{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Walking Robot Simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #simulation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #模拟"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: robotSim"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #模拟行走机器人"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>机器人在一个无限大小的 XY 网格平面上行走，从点&nbsp;<code>(0, 0)</code> 处开始出发，面向北方。该机器人可以接收以下三种类型的命令 <code>commands</code> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>-2</code> ：向左转&nbsp;<code>90</code> 度</li>\n",
    "\t<li><code>-1</code> ：向右转 <code>90</code> 度</li>\n",
    "\t<li><code>1 &lt;= x &lt;= 9</code> ：向前移动&nbsp;<code>x</code>&nbsp;个单位长度</li>\n",
    "</ul>\n",
    "\n",
    "<p>在网格上有一些格子被视为障碍物&nbsp;<code>obstacles</code> 。第 <code>i</code>&nbsp;个障碍物位于网格点 &nbsp;<code>obstacles[i] = (x<sub>i</sub>, y<sub>i</sub>)</code> 。</p>\n",
    "\n",
    "<p>机器人无法走到障碍物上，它将会停留在障碍物的前一个网格方块上，并继续执行下一个命令。</p>\n",
    "\n",
    "<p>返回机器人距离原点的 <strong>最大欧式距离</strong> 的 <strong>平方</strong> 。（即，如果距离为 <code>5</code> ，则返回 <code>25</code> ）</p>\n",
    "\n",
    "<div class=\"d-google dictRoot saladict-panel isAnimate\">\n",
    "<div>\n",
    "<div class=\"MachineTrans-Text\">\n",
    "<div class=\"MachineTrans-Lines\">\n",
    "<div class=\"MachineTrans-Lines-collapse MachineTrans-lang-en\">&nbsp;</div>\n",
    "</div>\n",
    "\n",
    "<div class=\"MachineTrans-Lines\">\n",
    "<p class=\"MachineTrans-lang-zh-CN\"><strong>注意：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li class=\"MachineTrans-lang-zh-CN\">北方表示 +Y 方向。</li>\n",
    "\t<li class=\"MachineTrans-lang-zh-CN\">东方表示 +X 方向。</li>\n",
    "\t<li class=\"MachineTrans-lang-zh-CN\">南方表示 -Y 方向。</li>\n",
    "\t<li class=\"MachineTrans-lang-zh-CN\">西方表示 -X 方向。</li>\n",
    "\t<li class=\"MachineTrans-lang-zh-CN\">原点 [0,0] 可能会有障碍物。</li>\n",
    "</ul>\n",
    "</div>\n",
    "</div>\n",
    "</div>\n",
    "</div>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>commands = [4,-1,3], obstacles = []\n",
    "<strong>输出：</strong>25\n",
    "<strong>解释：\n",
    "</strong>机器人开始位于 (0, 0)：\n",
    "1. 向北移动 4 个单位，到达 (0, 4)\n",
    "2. 右转\n",
    "3. 向东移动 3 个单位，到达 (3, 4)\n",
    "距离原点最远的是 (3, 4) ，距离为 3<sup>2</sup> + 4<sup>2</sup> = 25</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>commands = [4,-1,4,-2,4], obstacles = [[2,4]]\n",
    "<strong>输出：</strong>65\n",
    "<strong>解释</strong>：机器人开始位于 (0, 0)：\n",
    "1. 向北移动 4 个单位，到达 (0, 4)\n",
    "2. 右转\n",
    "3. 向东移动 1 个单位，然后被位于 (2, 4) 的障碍物阻挡，机器人停在 (1, 4)\n",
    "4. 左转\n",
    "5. 向北走 4 个单位，到达 (1, 8)\n",
    "距离原点最远的是 (1, 8) ，距离为 1<sup>2</sup> + 8<sup>2</sup> = 65</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>commands = [6,-1,-1,6], obstacles = []\n",
    "<b>输出：</b>36\n",
    "<b>解释：</b>机器人开始位于 (0, 0):\n",
    "1. 向北移动 6 个单位，到达 (0, 6).\n",
    "2. 右转\n",
    "3. 右转\n",
    "4. 向南移动 6 个单位，到达 (0, 0).\n",
    "机器人距离原点最远的点是 (0, 6)，其距离的平方是 6<sup>2</sup> = 36 个单位。</pre>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= commands.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>commands[i]</code> 的值可以取 <code>-2</code>、<code>-1</code> 或者是范围 <code>[1, 9]</code> 内的一个整数。</li>\n",
    "\t<li><code>0 &lt;= obstacles.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>-3 * 10<sup>4</sup> &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= 3 * 10<sup>4</sup></code></li>\n",
    "\t<li>答案保证小于 <code>2<sup>31</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [walking-robot-simulation](https://leetcode.cn/problems/walking-robot-simulation/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [walking-robot-simulation](https://leetcode.cn/problems/walking-robot-simulation/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,-1,3]\\n[]', '[4,-1,4,-2,4]\\n[[2,4]]', '[6,-1,-1,6]\\n[]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        # return [1,2] in obstacles\n",
    "        obstacles.sort(key = lambda x:(x[0],x[1]))\n",
    "        n=len(obstacles)\n",
    "        def check(x,y):\n",
    "            if n==0:return True\n",
    "            l,r=0,n-1\n",
    "            while l<r:\n",
    "                mid=(r-l)//2+l \n",
    "                if obstacles[mid][0]>=x:\n",
    "                    r=mid \n",
    "                else:\n",
    "                    l=mid+1\n",
    "            if obstacles[l][0]!=x:\n",
    "                return True\n",
    "            # l,r=0,n-1\n",
    "            r=l \n",
    "            while r<n and obstacles[r][0]==x:\n",
    "                r+=1\n",
    "            r-=1\n",
    "\n",
    "            while l<r:\n",
    "                mid=(r-l)//2+l \n",
    "                if obstacles[mid][1]>=y:\n",
    "                    r=mid \n",
    "                else:\n",
    "                    l=mid+1\n",
    "            if obstacles[l][1]!=y:\n",
    "                return True\n",
    "            return False\n",
    "        # print(check(2,4))\n",
    "        direction=[[0,1],[1,0],[0,-1],[-1,0]]\n",
    "        curd=0\n",
    "        x,y=0,0\n",
    "        ans=0\n",
    "        # flag=False\n",
    "        temp=list()\n",
    "        for cmd in commands:\n",
    "            if cmd<0:\n",
    "                curd+=1 if cmd==-1 else 3\n",
    "                curd%=4\n",
    "            else:\n",
    "                while cmd>0 and check(x+direction[curd][0],y+direction[curd][1]):\n",
    "                    x+=direction[curd][0]\n",
    "                    y+=direction[curd][1]\n",
    "                    cmd-=1\n",
    "                ans=max(ans,x**2+y**2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        steps = [(0,1),(-1,0),(0,-1),(1,0)]\n",
    "        x,y=0,0\n",
    "        max_distance=0\n",
    "        idd=0 #id of dir \n",
    "        d = {}\n",
    "        for a,b in obstacles:\n",
    "            d[(a,b)]=1\n",
    "\n",
    "        for c in commands:\n",
    "            if c==-2:\n",
    "                idd=(idd+1)%4\n",
    "            elif c==-1:\n",
    "                idd=(idd-1)%4\n",
    "            else:\n",
    "                delta_x, delta_y=steps[idd][0],steps[idd][1]\n",
    "                print(delta_x, delta_y)\n",
    "                for s in range(c):\n",
    "                    #试探向前走一步\n",
    "                    x_next=x + delta_x\n",
    "                    y_next=y + delta_y\n",
    "                    #print(\"试探位置是{},{}\".format(x_next,x_next))\n",
    "                    if (x_next,y_next) in d:\n",
    "                        break\n",
    "                    else:\n",
    "                        x,y=x_next,y_next\n",
    "                        #print(\"位置是{},{}\".format(x,y))\n",
    "                        max_distance=max(max_distance,x*x+y*y)\n",
    "\n",
    "        return max_distance\n",
    "\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        obs = set()\n",
    "\n",
    "        for obstacle in obstacles:\n",
    "            obs.add(str(obstacle[0]) + ',' + str(obstacle[1]))\n",
    "\n",
    "        x, y = 0, 0\n",
    "        dir = 0\n",
    "        ans = 0\n",
    "        dx = [0, 1, 0, -1]\n",
    "        dy = [1, 0, -1, 0]\n",
    "\n",
    "        for com in commands:\n",
    "            if com == -1:\n",
    "                dir = (dir+1)%4\n",
    "            elif com == -2:\n",
    "                dir = (dir+3)%4\n",
    "            else:\n",
    "                for i in range(com):\n",
    "                    nx = x + dx[dir]\n",
    "                    ny = y + dy[dir]\n",
    "                    h = str(nx) + ',' + str(ny)\n",
    "                    if h in obs:\n",
    "                        break\n",
    "                    x, y = nx, ny\n",
    "                    ans = max(ans, x*x + y*y)\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        loc, d, res = 0, 1j, 0\n",
    "        obs = set(map(lambda x:x[0]+x[1]*1j, obstacles))\n",
    "        res = 0\n",
    "        for c in commands:\n",
    "            if c < 0:\n",
    "                d *= (- 3 - 2 * c)*1j\n",
    "                continue\n",
    "            for i in range(c):\n",
    "                if loc + d in obs:\n",
    "                    break\n",
    "                loc += d \n",
    "            res = max(res,loc.real ** 2 + loc.imag ** 2)\n",
    "        return int(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        #commands = [4,-1,4,-2,4]\n",
    "        #obstacles = [[2,4]]\n",
    "        obstaclesSet = set()\n",
    "        for obstacle in obstacles:\n",
    "            obstaclesSet.add(str(obstacle[0])+','+str(obstacle[1]))\n",
    "        x,y = 0,0\n",
    "        # 0-->+y  1-->+x    2-->-y  3--> -x\n",
    "        ans, direction = 0,0\n",
    "        dx = [0,1,0,-1]\n",
    "        dy = [1,0,-1,0]\n",
    "        for command in commands:\n",
    "            if command == -2:\n",
    "                direction = (direction+3)%4\n",
    "            elif command == -1:\n",
    "                direction = (direction+1)%4\n",
    "            else:\n",
    "                for i in range(command):\n",
    "                    nx = x+dx[direction]\n",
    "                    ny = y+dy[direction]\n",
    "                    tmp = str(nx)+','+str(ny)\n",
    "                    if tmp not in obstaclesSet:\n",
    "                        x,y = nx,ny\n",
    "                    else:\n",
    "                        break\n",
    "                ans = max(ans, x**2+y**2)\n",
    "        return ans\n",
    "        '''\n",
    "        x,y = 0,0\n",
    "        # 0-->+y  1-->+x    2-->-y  3--> -x  \n",
    "        direction = 0\n",
    "        ans = 0\n",
    "        for command in commands:\n",
    "            if command == -2:\n",
    "                if direction == 0:\n",
    "                    direction = 3\n",
    "                elif direction == 1:\n",
    "                    direction = 0\n",
    "                elif direction == 2:\n",
    "                    direction = 1\n",
    "                elif direction == 3:\n",
    "                    direction = 2\n",
    "            elif command == -1:\n",
    "                if direction == 0:\n",
    "                    direction = 1\n",
    "                elif direction == 1:\n",
    "                    direction = 2\n",
    "                elif direction == 2:\n",
    "                    direction = 3\n",
    "                elif direction == 3:\n",
    "                    direction = 0\n",
    "            else:\n",
    "                if direction == 0:\n",
    "                    update = False\n",
    "                    target = y+command\n",
    "                    for a,b in obstacles:\n",
    "                        if a == x and y < b and y+command >= b:\n",
    "                            update = True\n",
    "                            target = min(target,b-1)\n",
    "                    if not update:\n",
    "                        y += command\n",
    "                    else:\n",
    "                        y = target\n",
    "                elif direction == 1:\n",
    "                    update = False\n",
    "                    target = x+command\n",
    "                    for a,b in obstacles:\n",
    "                        if b == y and x < a and x+command >= a:\n",
    "                            update = True\n",
    "                            target = min(target,a-1)\n",
    "                    if not update:\n",
    "                        x += command\n",
    "                    else:\n",
    "                        x = target\n",
    "                elif direction == 2:\n",
    "                    update = False\n",
    "                    target = y-command\n",
    "                    for a,b in obstacles:\n",
    "                        if a == x and y > b and y-command <= b:\n",
    "                            update = True\n",
    "                            target = max(target,b+1)\n",
    "                    if not update:\n",
    "                        y -= command\n",
    "                    else:\n",
    "                        y = target\n",
    "                elif direction == 3:\n",
    "                    update = False\n",
    "                    target = x-command\n",
    "                    for a,b in obstacles:\n",
    "                        if b == y and x > a and x-command <= a:\n",
    "                            update = True\n",
    "                            target = max(target,a+1)\n",
    "                    if not update:\n",
    "                        x -= command\n",
    "                    else:\n",
    "                        x = target\n",
    "            ans = max(ans, abs(x**2+y**2))\n",
    "            #print(x,y,direction)\n",
    "        return ans\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        diret_x, diret_y = 0, 0\n",
    "        pos_x, pos_y = 0, 0\n",
    "        ret = 0\n",
    "        obs_dict = {}\n",
    "        for i in obstacles:\n",
    "            obs_dict[tuple(i)] = 0\n",
    "        for command in commands:\n",
    "            if command == -1:\n",
    "                diret_x += math.pi / 2\n",
    "                diret_y += math.pi / 2\n",
    "            elif command == -2:\n",
    "                diret_x -= math.pi / 2\n",
    "                diret_y -= math.pi / 2\n",
    "            else:\n",
    "                delta_x, delta_y = int(math.sin(diret_x)), int(math.cos(diret_y))\n",
    "                for _ in range(command):\n",
    "                    next_pos = (pos_x + delta_x, pos_y + delta_y)\n",
    "                    if next_pos in obs_dict:\n",
    "                        break\n",
    "                    pos_x, pos_y = next_pos\n",
    "                print(pos_x, pos_y)\n",
    "                ret = max(ret, int(pos_x**2 + pos_y**2 ))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        # 暴力解法--遍历每个位置\n",
    "        # 每次最多走9步 最多10^4次-->所以最多有9*10^4步--计算每步的位置到原点的距离\n",
    "        # 技巧1:\n",
    "        # 使用set存储障碍物{(x1,y1),...}而不是使用数组(因为数组的查询O(n))但因为不确定是否可以对tuple进行hash(Python可以) 但一定可以对int和string进行hash-->所以先将tuple转换成string\n",
    "            # int:使用进制数 \n",
    "                # 先+30000防止进制数中有负数:(x+30000,y+30000)\n",
    "                # xi yi最多3*10^4-->相当于30000进制 现在多+30000变成了60000进制数;(x+30000)=十位 *10^1；(y+30000)=个位 *10^0=1\n",
    "                # 大整数=(x+30000)*(60000)+(y+30000)--此时可以求hash\n",
    "            # string:xy拼接 \n",
    "                # (-200,30000)-->\"-200,30000\"--此时可以求hash\n",
    "        blockers = set()\n",
    "        for obs in obstacles: #obs=[2,4]\n",
    "            blockers.add(self.calcHash(obs[0],obs[1])) #add 可以hash的值\n",
    "        \n",
    "        # 技巧2：\n",
    "        # 使用方向数组 避免每次的方向if判断\n",
    "            # 偏移量--单位向量\n",
    "        # if N:x走0 y走1\n",
    "        #       N E S W\n",
    "        dirx = [0,1,0,-1]\n",
    "        diry = [1,0,-1,0]\n",
    "        # 初始位置\n",
    "        x = 0\n",
    "        y = 0\n",
    "        dir = 0 #刚开始的方向--N\n",
    "        ans = 0\n",
    "\n",
    "        for cmd in commands:\n",
    "            if cmd > 0: #移动1--9\n",
    "                # 遍历移动的每一步\n",
    "                for i in range(cmd): #0--cmd-1总共cmd步\n",
    "                    # 这里不能直接修改x(x+=dirx[dir])--因为需要对nextx进行预判！\n",
    "                    # 如果nextx是障碍 则x仍然是x x-->nextx这一步不能走！\n",
    "                        # 所以是尝试走到nextx\n",
    "                    # 向dir方向走一步 就+dir的偏移量\n",
    "                    nextx = x + dirx[dir] #x走一步\n",
    "                    nexty = y + diry[dir] #y走一步\n",
    "                    # 判断是否遇到障碍\n",
    "                    if self.calcHash(nextx,nexty) in blockers:\n",
    "                        break #从当前的for loop中break 跳到下一个cmd #此时x仍然是障碍前一个\n",
    "                    # 不是障碍才能真的走这一步\n",
    "                    x = nextx\n",
    "                    y = nexty\n",
    "                    # 每个位置都要计算到原点的距离\n",
    "                    ans = max(ans,x*x+y*y)\n",
    "                \n",
    "            elif cmd == -1: #右转 N0->E1->S2->W3->N0\n",
    "                dir = (dir + 1)%4 #循环的队列中 向右走一步 (x+1)%len\n",
    "            else: #-2 左转 N0->W3->S2->E1->N0\n",
    "                dir = (dir - 1 + 4)%4 #-1会出现负数 故+mod数 是一样的\n",
    "        return ans\n",
    "\n",
    "\n",
    "    def calcHash(self,x,y):\n",
    "        return str(x)+\",\"+str(y)\n",
    "        # return (x+30000)*60000 + y + 30000 # int\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        cur_pos = [0, 0]\n",
    "        cur_dir = [0, 1]\n",
    "        max_distance = 0\n",
    "        obs_dic = {}\n",
    "        for obs in obstacles:\n",
    "            obs_dic[(obs[0], obs[1])] = 1\n",
    "        # cur_pos表示位置，cur_dir表示方向\n",
    "        # 模拟一遍指令\n",
    "        for ins in commands:\n",
    "            if ins > 0:\n",
    "                # 尝试走这段距离，直到遇到障碍或走完\n",
    "                while ins > 0:\n",
    "                    try_pos = (cur_pos[0] + cur_dir[0], cur_pos[1] + cur_dir[1])\n",
    "                    if try_pos not in obs_dic:\n",
    "                        cur_pos[0] = try_pos[0]\n",
    "                        cur_pos[1] = try_pos[1]\n",
    "                        ins -= 1\n",
    "                    else:\n",
    "                        break\n",
    "                # 更新最大距离（中间的点一定不是最远点）\n",
    "                print(cur_pos)\n",
    "                max_distance = max(max_distance, cur_pos[0]**2 + cur_pos[1]**2)\n",
    "            elif ins == -2:\n",
    "                cur_dir[0], cur_dir[1] = -cur_dir[1], cur_dir[0]\n",
    "            elif ins == -1:\n",
    "                cur_dir[0], cur_dir[1] = cur_dir[1], -cur_dir[0]\n",
    "        return max_distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        d = [(1, 0),(0, 1),(-1, 0),(0, -1)] # 逆\n",
    "        \n",
    "        c1 = collections.defaultdict(list)\n",
    "        c2 = collections.defaultdict(list)\n",
    "        for x, y in obstacles:\n",
    "            insort(c1[x], y)\n",
    "            insort(c2[y], x)\n",
    "        def nex_pos(x, y, dx, index):\n",
    "            if index == 0:\n",
    "                # 二分查找对应的障碍物\n",
    "                idx = bisect.bisect(c2[y], x)\n",
    "                if idx == len(c2[y]) or c2[y][idx] > x + dx:\n",
    "                    return (x+dx, y)\n",
    "                return (c2[y][idx] - 1, y)\n",
    "            elif index == 1:\n",
    "                idx = bisect.bisect(c1[x], y)\n",
    "                if idx == len(c1[x]) or c1[x][idx] > y + dx:\n",
    "                    return (x, y+dx)\n",
    "                return (x, c1[x][idx] - 1)\n",
    "            elif index == 2:\n",
    "                idx = bisect.bisect_left(c2[y], x)\n",
    "                if idx == 0 or c2[y][idx-1] < x - dx:\n",
    "                    return (x-dx, y)\n",
    "                return (c2[y][idx-1]+1, y)\n",
    "            elif index == 3:\n",
    "                idx = bisect.bisect_left(c1[x], y)\n",
    "                if idx == 0 or c1[x][idx-1] < y - dx:\n",
    "                    return (x, y-dx)\n",
    "                return (x, c1[x][idx-1]+1)\n",
    "        ans,index,x,y = 0, 1, 0, 0\n",
    "        for num in commands:\n",
    "            if num == -1:\n",
    "                index = (index - 1) % 4\n",
    "            elif num == -2:\n",
    "                index = (index + 1) % 4\n",
    "            else:\n",
    "                x, y = nex_pos(x, y ,num, index)\n",
    "                \n",
    "                ans = max(ans, x * x + y * y)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        x1 = [0, 1, 0, -1]\n",
    "        y1 = [1, 0, -1, 0]\n",
    "        i = 0\n",
    "        x = y = 0\n",
    "        res = 0\n",
    "        obstacles = {(x, y) for x, y in obstacles}\n",
    "        print(obstacles)\n",
    "        for cmd in commands:\n",
    "            if cmd == -1:\n",
    "                i = (i + 1) % 4\n",
    "            elif cmd == -2:\n",
    "                i = (i + 3) % 4\n",
    "            else:\n",
    "                dx = x1[i]\n",
    "                dy = y1[i]                 \n",
    "                for _ in range(cmd):\n",
    "                    if (x + dx, y + dy) in obstacles:\n",
    "                        break\n",
    "                    else:\n",
    "                        x += dx\n",
    "                        y += dy\n",
    "                    res = max(res, x**2 + y**2)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        flag=1\n",
    "        coordinate=[0,0]\n",
    "        distance=0\n",
    "\n",
    "        obstacles1,obstacles2={},{}\n",
    "        for i in range(len(obstacles)):\n",
    "            if obstacles[i][0] not in obstacles1:\n",
    "                obstacles1[obstacles[i][0]]=[obstacles[i][1]]\n",
    "            else:\n",
    "                obstacles1[obstacles[i][0]].append(obstacles[i][1])\n",
    "        for i in range(len(obstacles)):\n",
    "            if obstacles[i][1] not in obstacles2:\n",
    "                obstacles2[obstacles[i][1]]=[obstacles[i][0]]\n",
    "            else:\n",
    "                obstacles2[obstacles[i][1]].append(obstacles[i][0])\n",
    "        for i in range(len(commands)):\n",
    "            if commands[i]>0:\n",
    "                if flag%4==1:\n",
    "                    coordinate=self.exist_obs(coordinate,commands[i],obstacles1,1)\n",
    "                elif flag%4==2:\n",
    "                    coordinate=self.exist_obs(coordinate,commands[i],obstacles2,2)\n",
    "\n",
    "                elif flag%4==3:\n",
    "                    coordinate=self.exist_obs(coordinate,commands[i],obstacles1,3)\n",
    "\n",
    "                elif flag%4==0:\n",
    "                    coordinate=self.exist_obs(coordinate,commands[i],obstacles2,0)\n",
    "\n",
    "                distance=max(distance,coordinate[0]**2+coordinate[1]**2)\n",
    "                print(coordinate)\n",
    "            elif commands[i]==-1:\n",
    "                flag+=1\n",
    "            elif commands[i]==-2:\n",
    "                flag-=1\n",
    "        return distance\n",
    "\n",
    "    def exist_obs(self,coordinate,command,obs,flag):\n",
    "        if flag==1:\n",
    "            if coordinate[0] in obs:\n",
    "                obst=obs[coordinate[0]]\n",
    "                for i in range(len(obst)):\n",
    "                    if obst[i]<=(coordinate[1]+command) and obst[i]>coordinate[1]:\n",
    "                        return [coordinate[0],obst[i]-1]\n",
    "            return [coordinate[0],coordinate[1]+command]\n",
    "        if flag==3:\n",
    "            if coordinate[0] in obs:\n",
    "                obst=obs[coordinate[0]]\n",
    "                for i in range(len(obst)):\n",
    "                    if obst[i]>=(coordinate[1]-command) and obst[i]<coordinate[1]:\n",
    "                        return [coordinate[0],obst[i]+1]\n",
    "            return [coordinate[0],coordinate[1]-command]\n",
    "        if flag==2:\n",
    "            if coordinate[1] in obs:\n",
    "                obst=obs[coordinate[1]]\n",
    "                for i in range(len(obst)):\n",
    "                    if obst[i]<=(coordinate[0]+command) and obst[i]>coordinate[0]:\n",
    "                        return [obst[i]-1,coordinate[1]]\n",
    "            return [coordinate[0]+command,coordinate[1]]\n",
    "        if flag==0:\n",
    "            if coordinate[1] in obs:\n",
    "                obst=obs[coordinate[1]]\n",
    "                for i in range(len(obst)):\n",
    "                    if obst[i]>=(coordinate[0]-command) and obst[i]<coordinate[0]:\n",
    "                        return [obst[i]+1,coordinate[1]]\n",
    "            return [coordinate[0]-command,coordinate[1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        obstacles.sort(key=lambda x:x[0])\n",
    "        def check(x, y, obstacles):\n",
    "            left, right = 0, len(obstacles)-1\n",
    "            while left<=right:\n",
    "                mid = left+(right-left)//2\n",
    "                if obstacles[mid][0]<=x:left=mid+1\n",
    "                else:right = mid-1\n",
    "            left-=1\n",
    "            while left>=0 and obstacles[left][0] == x:\n",
    "                if obstacles[left][1] == y: return False\n",
    "                left-=1\n",
    "            return True\n",
    "\n",
    "        ans = 0\n",
    "        flag = 0\n",
    "        pos = [0,0]\n",
    "        for com in commands:\n",
    "            if com == -1:flag = (flag+1)%4\n",
    "            elif com == -2: flag = (flag-1+4)%4\n",
    "            else:\n",
    "                if flag == 0:\n",
    "                    for i in range(1, com+1):\n",
    "                        if(check(pos[0], pos[1]+1, obstacles)):pos[1]+=1\n",
    "                        else:break\n",
    "                elif flag == 1:\n",
    "                    for i in range(1, com+1):\n",
    "                        if(check(pos[0]+1, pos[1],obstacles)):pos[0]+=1\n",
    "                        else:break\n",
    "                elif flag == 2:\n",
    "                    for i in range(1, com+1):\n",
    "                        if(check(pos[0], pos[1]-1, obstacles)):pos[1]-=1\n",
    "                        else:break\n",
    "                else:\n",
    "                    for i in range(1, com+1):\n",
    "                        if(check(pos[0]-1, pos[1], obstacles)):pos[0]-=1\n",
    "                        else:break\n",
    "            ans = max(ans, pos[0]*pos[0]+pos[1]*pos[1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:    \n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        point = [0, 0]\n",
    "        max_ans = 0\n",
    "        direction = 0\n",
    "        delta_distance_dict = {0:1, 1:1, 2:-1, 3:-1}\n",
    "        x = [[row[0] for row in obstacles], [row[1] for row in obstacles]]\n",
    "        for i in commands:\n",
    "            if i in (-1, -2):\n",
    "                direction = (direction - (2*i+1)) % 4\n",
    "                continue\n",
    "            else:\n",
    "                if point[direction % 2] not in x[direction % 2]:\n",
    "                    point[1 - direction % 2] += delta_distance_dict[direction] * i\n",
    "                else:\n",
    "                    for _ in range(i):\n",
    "                        point[1 - direction % 2] += delta_distance_dict[direction]\n",
    "                        if point in obstacles:\n",
    "                            point[1 - direction % 2] -= delta_distance_dict[direction]\n",
    "                            break\n",
    "                max_ans = max(point[0]*point[0]+point[1]*point[1], max_ans)\n",
    "        return max_ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        flag = 0\n",
    "        x, y = 0, 0\n",
    "        obsx = [o[0] for o in obstacles]\n",
    "        obsy = [o[1] for o in obstacles]\n",
    "        d = 0\n",
    "        for c in commands:\n",
    "            if c==-2:\n",
    "                flag=(flag-1)%4\n",
    "            if c==-1:\n",
    "                flag=(flag+1)%4\n",
    "            if c>0:\n",
    "                if flag == 0:\n",
    "                    if x in obsx:\n",
    "                        xi = [i for i,v in enumerate(obsx) if v==x]\n",
    "                        yi = [obsy[v] for v in xi]\n",
    "                        yi.sort()\n",
    "                        i = 0\n",
    "                        while i < len(yi) and yi[i]<=y:\n",
    "                            i = i+1\n",
    "                        if i == len(yi):\n",
    "                            y = y+c\n",
    "                            d = max(d,x**2+y**2)\n",
    "                            continue\n",
    "                        y = min(y+c, yi[i]-1)\n",
    "                    else:\n",
    "                        y = y+c\n",
    "                if flag == 1:\n",
    "                    if y in obsy:\n",
    "                        yi = [i for i,v in enumerate(obsy) if v==y]\n",
    "                        xi = [obsx[v] for v in yi]\n",
    "                        xi.sort()\n",
    "                        i = 0\n",
    "                        while i < len(xi) and xi[i]<=x:\n",
    "                            i = i+1\n",
    "                        if i == len(xi):\n",
    "                            x = x+c\n",
    "                            d = max(d,x**2+y**2)\n",
    "                            continue\n",
    "                        x = min(x+c, xi[i]-1)\n",
    "                    else:\n",
    "                        x = x+c\n",
    "                if flag == 2:\n",
    "                    if x in obsx: \n",
    "                        xi = [i for i,v in enumerate(obsx) if v==x]\n",
    "                        yi = [obsy[v] for v in xi]\n",
    "                        yi.sort(reverse = True)\n",
    "                        i = 0\n",
    "                        while i < len(yi) and yi[i]>=y:\n",
    "                            i = i+1\n",
    "                        if i == len(yi):\n",
    "                            y = y-c\n",
    "                            d = max(d,x**2+y**2)\n",
    "                            continue\n",
    "                        y = max(y-c, yi[i]+1)\n",
    "                    else:\n",
    "                        y = y-c\n",
    "                if flag == 3:\n",
    "                    if y in obsy:\n",
    "                        yi = [i for i,v in enumerate(obsy) if v==y]\n",
    "                        xi = [obsx[v] for v in yi]\n",
    "                        xi.sort(reverse = True)\n",
    "                        i = 0\n",
    "                        while i < len(xi) and xi[i]>=x:\n",
    "                            i = i+1\n",
    "                        if i == len(xi):\n",
    "                            x = x-c\n",
    "                            d = max(d,x**2+y**2)\n",
    "                            continue\n",
    "                        x = max(x-c, xi[i]+1)\n",
    "                    else:\n",
    "                        x = x-c\n",
    "            d = max(d,x**2+y**2)\n",
    "        return d\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        # return [1,2] in obstacles\n",
    "        obstacles.sort(key = lambda x:(x[0],x[1]))\n",
    "        n=len(obstacles)\n",
    "        def check(x,y):\n",
    "            if n==0:return True\n",
    "            l,r=0,n-1\n",
    "            while l<r:\n",
    "                mid=(r-l)//2+l \n",
    "                if obstacles[mid][0]>=x:\n",
    "                    r=mid \n",
    "                else:\n",
    "                    l=mid+1\n",
    "            if obstacles[l][0]!=x:\n",
    "                return True\n",
    "            # l,r=0,n-1\n",
    "            r=l \n",
    "            while r<n and obstacles[r][0]==x:\n",
    "                r+=1\n",
    "            r-=1\n",
    "\n",
    "            while l<r:\n",
    "                mid=(r-l)//2+l \n",
    "                if obstacles[mid][1]>=y:\n",
    "                    r=mid \n",
    "                else:\n",
    "                    l=mid+1\n",
    "            if obstacles[l][1]!=y:\n",
    "                return True\n",
    "            return False\n",
    "        # print(check(2,4))\n",
    "        direction=[[0,1],[1,0],[0,-1],[-1,0]]\n",
    "        curd=0\n",
    "        x,y=0,0\n",
    "        ans=0\n",
    "        # flag=False\n",
    "        temp=list()\n",
    "        for cmd in commands:\n",
    "            if cmd<0:\n",
    "                # while flag and [x,y] in obstacles :\n",
    "                #     x-=direction[curd][0]\n",
    "                #     y-=direction[curd][1]\n",
    "                if cmd==-1:\n",
    "                    curd=(curd+1)%4\n",
    "                else:\n",
    "                    curd=(curd+3)%4\n",
    "            else:\n",
    "            #temp.append(check(x+direction[curd][0],y+direction[curd][1]))\n",
    "                while cmd>0 and check(x+direction[curd][0],y+direction[curd][1]):\n",
    "                    x+=direction[curd][0]\n",
    "                    y+=direction[curd][1]\n",
    "                    cmd-=1\n",
    "                ans=max(ans,x**2+y**2)\n",
    "            #temp.append(check(x+direction[curd][0],y+direction[curd][1]))\n",
    "        # print(temp)\n",
    "        # print(obstacles)\n",
    "        # print(check(0,1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        flag = 0\n",
    "        x, y = 0, 0\n",
    "        obsx = [o[0] for o in obstacles]\n",
    "        obsy = [o[1] for o in obstacles]\n",
    "        d = 0\n",
    "        for c in commands:\n",
    "            if c==-2:\n",
    "                flag=(flag-1)%4\n",
    "            if c==-1:\n",
    "                flag=(flag+1)%4\n",
    "            if c>0:\n",
    "                if flag == 0:\n",
    "                    if x in obsx:\n",
    "                        xi = [i for i,v in enumerate(obsx) if v==x]\n",
    "                        yi = [obsy[v] for v in xi]\n",
    "                        yi.sort()\n",
    "                        i = 0\n",
    "                        while i < len(yi) and yi[i]<=y:\n",
    "                            i = i+1\n",
    "                        if i == len(yi):\n",
    "                            y = y+c\n",
    "                            d = max(d,x**2+y**2)\n",
    "                            continue\n",
    "                        y = min(y+c, yi[i]-1)\n",
    "                    else:\n",
    "                        y = y+c\n",
    "                if flag == 1:\n",
    "                    if y in obsy:\n",
    "                        yi = [i for i,v in enumerate(obsy) if v==y]\n",
    "                        xi = [obsx[v] for v in yi]\n",
    "                        xi.sort()\n",
    "                        i = 0\n",
    "                        while i < len(xi) and xi[i]<=x:\n",
    "                            i = i+1\n",
    "                        if i == len(xi):\n",
    "                            x = x+c\n",
    "                            d = max(d,x**2+y**2)\n",
    "                            continue\n",
    "                        x = min(x+c, xi[i]-1)\n",
    "                    else:\n",
    "                        x = x+c\n",
    "                if flag == 2:\n",
    "                    if x in obsx: \n",
    "                        xi = [i for i,v in enumerate(obsx) if v==x]\n",
    "                        yi = [obsy[v] for v in xi]\n",
    "                        yi.sort(reverse = True)\n",
    "                        i = 0\n",
    "                        while i < len(yi) and yi[i]>=y:\n",
    "                            i = i+1\n",
    "                        if i == len(yi):\n",
    "                            y = y-c\n",
    "                            d = max(d,x**2+y**2)\n",
    "                            continue\n",
    "                        y = max(y-c, yi[i]+1)\n",
    "                    else:\n",
    "                        y = y-c\n",
    "                if flag == 3:\n",
    "                    if y in obsy:\n",
    "                        yi = [i for i,v in enumerate(obsy) if v==y]\n",
    "                        xi = [obsx[v] for v in yi]\n",
    "                        xi.sort(reverse = True)\n",
    "                        i = 0\n",
    "                        while i < len(xi) and xi[i]>=x:\n",
    "                            i = i+1\n",
    "                        if i == len(xi):\n",
    "                            x = x-c\n",
    "                            d = max(d,x**2+y**2)\n",
    "                            continue\n",
    "                        x = max(x-c, xi[i]+1)\n",
    "                    else:\n",
    "                        x = x-c\n",
    "            d = max(d,x**2+y**2)\n",
    "        return d\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        hash_x = {}\n",
    "        hash_y = {}\n",
    "        for i,j in obstacles:\n",
    "            if i not in hash_x:\n",
    "                hash_x[i] = []\n",
    "            hash_x[i].append(j)\n",
    "            if j not in hash_y:\n",
    "                hash_y[j] = []\n",
    "            hash_y[j].append(i)\n",
    "        for k in hash_x:\n",
    "            hash_x[k].sort()\n",
    "        for k in hash_y:\n",
    "            hash_y[k].sort()\n",
    "        dx = [0, 1, 0, -1]\n",
    "        dy = [1, 0, -1, 0]\n",
    "        x=y=cur=0\n",
    "        for g in commands:\n",
    "            if g == -2:\n",
    "                cur = (cur-1+4) % 4\n",
    "            elif g == -1:\n",
    "                cur = (cur+1) % 4\n",
    "            else:\n",
    "                if cur == 0:\n",
    "                    up = float('inf')\n",
    "                    for ob in hash_x.get(x, []):\n",
    "                        if ob > y:\n",
    "                            up = ob\n",
    "                            break \n",
    "                    x = x\n",
    "                    y = min(y+g, up-1)\n",
    "                elif cur == 1:\n",
    "                    right = float('inf')\n",
    "                    for t in range(len(hash_y.get(y, []))):\n",
    "                        if  hash_y[y][t]> x:\n",
    "                            right = hash_y[y][t]\n",
    "                            break\n",
    "                    y = y\n",
    "                    x = min(x+g, right-1)\n",
    "                elif cur == 2:           \n",
    "                    bot = float('-inf')\n",
    "                    for t in range(len(hash_x.get(x, []))-1, -1, -1):\n",
    "                        if  hash_x[x][t] < y:\n",
    "                            bot = hash_x[x][t]\n",
    "                            break\n",
    "                    x = x\n",
    "                    y = max(y-g, bot+1)      \n",
    "                else:\n",
    "                    left = float('-inf')\n",
    "                    for t in range(len(hash_y.get(y, []))-1, -1, -1):\n",
    "                        if  hash_y[y][t] < x:\n",
    "                            left = hash_y[y][t]\n",
    "                            break\n",
    "                    y = y\n",
    "                    x = max(x-g, left+1)\n",
    "                res = max(res, x**2+y**2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        dic = {}\n",
    "        for coordinate in obstacles:\n",
    "            dic[str(coordinate[0])+' '+str(coordinate[1])] = 1\n",
    "        \n",
    "        \n",
    "        x = 0\n",
    "        y = 0\n",
    "        d = 0\n",
    "        direction = [[0,1],[1,0],[0,-1],[-1,0]]\n",
    "        maxN = 0\n",
    "\n",
    "        for c in commands:\n",
    "            if c == -2:\n",
    "                d = (d-1)%4\n",
    "            elif c == -1:\n",
    "                d = (d+1)%4\n",
    "            else:\n",
    "                tx,ty = direction[d]\n",
    "                for i in range(c):\n",
    "                    s = str(x+tx)+' '+str(y+ty)\n",
    "                    if s in dic:\n",
    "                        break\n",
    "                    else:\n",
    "                        x += tx\n",
    "                        y += ty\n",
    "                temp = x*x+y*y\n",
    "                if temp>maxN:\n",
    "                    maxN = temp\n",
    "        return maxN\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        current_point = [0, 0]\n",
    "        max_length = 0\n",
    "        current_direction = '+Y'\n",
    "        tmp_move_length = 0\n",
    "\n",
    "        for command in commands:\n",
    "            if command < 0:\n",
    "                if tmp_move_length > 0:\n",
    "                    current_point = self.check_obstacle(current_point, current_direction, tmp_move_length, obstacles)\n",
    "                    current_length = current_point[0] * current_point[0] + current_point[1] * current_point[1]\n",
    "                    if current_length > max_length:\n",
    "                        max_length = current_length\n",
    "                    tmp_move_length = 0\n",
    "                current_direction = self.change_direction(current_direction, command)                   \n",
    "            else:\n",
    "                tmp_move_length += command\n",
    "        \n",
    "        if tmp_move_length > 0:\n",
    "            current_point = self.check_obstacle(current_point, current_direction, tmp_move_length, obstacles)\n",
    "            current_length = current_point[0] * current_point[0] + current_point[1] * current_point[1]\n",
    "            if current_length > max_length:\n",
    "                max_length = current_length\n",
    "\n",
    "        return max_length\n",
    "    \n",
    "    def change_direction(self, current_direction, command):\n",
    "        if command == -1:\n",
    "            if current_direction == '+Y':\n",
    "                current_direction = '+X'\n",
    "            elif current_direction == '-Y':\n",
    "                current_direction = '-X'\n",
    "            elif current_direction == '+X':\n",
    "                current_direction = '-Y'\n",
    "            else:\n",
    "                current_direction = '+Y'\n",
    "        else:\n",
    "            if current_direction == '+Y':\n",
    "                current_direction = '-X'\n",
    "            elif current_direction == '-Y':\n",
    "                current_direction = '+X'\n",
    "            elif current_direction == '+X':\n",
    "                current_direction = '+Y'\n",
    "            else:\n",
    "                current_direction = '-Y'\n",
    "\n",
    "        return current_direction\n",
    "\n",
    "    def check_obstacle(self, current_point, current_direction, command, obstacles):\n",
    "        target_obstacle = None\n",
    "\n",
    "        if current_direction == '+X':\n",
    "            base_index, scan_index, flag = 1, 0, 1\n",
    "        elif current_direction == '-X':\n",
    "            base_index, scan_index, flag = 1, 0, -1\n",
    "        elif current_direction == '+Y':\n",
    "            base_index, scan_index, flag = 0, 1, 1\n",
    "        else:\n",
    "            base_index, scan_index, flag = 0, 1, -1\n",
    "        \n",
    "        for obstacle in obstacles:\n",
    "            if obstacle[base_index] == current_point[base_index] and flag*(obstacle[scan_index] - current_point[scan_index]) <= command and flag * (obstacle[scan_index] - current_point[scan_index]) > 0:\n",
    "                if target_obstacle is None or obstacle[scan_index] <= target_obstacle[scan_index]:\n",
    "                    target_obstacle = [0, 0]\n",
    "                    target_obstacle[base_index] = obstacle[base_index]\n",
    "                    target_obstacle[scan_index] = obstacle[scan_index] - flag\n",
    "        \n",
    "        if target_obstacle is None:\n",
    "            target_obstacle = [0, 0]\n",
    "            target_obstacle[base_index] = current_point[base_index]\n",
    "            target_obstacle[scan_index] = current_point[scan_index] + command * flag\n",
    "        \n",
    "        return target_obstacle\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        # return [1,2] in obstacles\n",
    "        obstacles.sort(key = lambda x:(x[0],x[1]))\n",
    "        n=len(obstacles)\n",
    "        def check(x,y):\n",
    "            if n==0:return True\n",
    "            l,r=0,n-1\n",
    "            while l<r:\n",
    "                mid=(r-l)//2+l \n",
    "                if obstacles[mid][0]>=x:\n",
    "                    r=mid \n",
    "                else:\n",
    "                    l=mid+1\n",
    "            if obstacles[l][0]!=x:\n",
    "                return True\n",
    "            # l,r=0,n-1\n",
    "            r=l \n",
    "            while r<n and obstacles[r][0]==x:\n",
    "                r+=1\n",
    "            r-=1\n",
    "\n",
    "            while l<r:\n",
    "                mid=(r-l)//2+l \n",
    "                if obstacles[mid][1]>=y:\n",
    "                    r=mid \n",
    "                else:\n",
    "                    l=mid+1\n",
    "            if obstacles[l][1]!=y:\n",
    "                return True\n",
    "            return False\n",
    "        # print(check(2,4))\n",
    "        direction=[[0,1],[1,0],[0,-1],[-1,0]]\n",
    "        curd=0\n",
    "        x,y=0,0\n",
    "        ans=0\n",
    "        # flag=False\n",
    "        temp=list()\n",
    "        for cmd in commands:\n",
    "            if cmd<0:\n",
    "                # while flag and [x,y] in obstacles :\n",
    "                #     x-=direction[curd][0]\n",
    "                #     y-=direction[curd][1]\n",
    "                if cmd==-1:\n",
    "                    curd=(curd+1)%4\n",
    "                else:\n",
    "                    curd=(curd+3)%4\n",
    "                continue\n",
    "            #temp.append(check(x+direction[curd][0],y+direction[curd][1]))\n",
    "            while cmd>0 and check(x+direction[curd][0],y+direction[curd][1]):\n",
    "                x+=direction[curd][0]\n",
    "                y+=direction[curd][1]\n",
    "                cmd-=1\n",
    "            ans=max(ans,x**2+y**2)\n",
    "            #temp.append(check(x+direction[curd][0],y+direction[curd][1]))\n",
    "        # print(temp)\n",
    "        # print(obstacles)\n",
    "        # print(check(0,1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        obstacles.sort(key=lambda x:x[0])\n",
    "        def check(x, y, obstacles):\n",
    "            left, right = 0, len(obstacles)-1\n",
    "            while left<=right:\n",
    "                mid = left+(right-left)//2\n",
    "                if obstacles[mid][0]<=x:left=mid+1\n",
    "                else:right = mid-1\n",
    "            left-=1\n",
    "            while left>=0 and obstacles[left][0] == x:\n",
    "                if obstacles[left][1] == y: return False\n",
    "                left-=1\n",
    "            return True\n",
    "\n",
    "        ans = 0\n",
    "        flag = 0\n",
    "        pos = [0,0]\n",
    "        for com in commands:\n",
    "            if com == -1:flag = (flag+1)%4\n",
    "            elif com == -2: flag = (flag-1+4)%4\n",
    "            else:\n",
    "                if flag == 0:\n",
    "                    for i in range(1, com+1):\n",
    "                        if(check(pos[0], pos[1]+1, obstacles)):pos[1]+=1\n",
    "                        else:break\n",
    "                elif flag == 1:\n",
    "                    for i in range(1, com+1):\n",
    "                        if(check(pos[0]+1, pos[1],obstacles)):pos[0]+=1\n",
    "                        else:break\n",
    "                elif flag == 2:\n",
    "                    for i in range(1, com+1):\n",
    "                        if(check(pos[0], pos[1]-1, obstacles)):pos[1]-=1\n",
    "                        else:break\n",
    "                else:\n",
    "                    for i in range(1, com+1):\n",
    "                        if(check(pos[0]-1, pos[1], obstacles)):pos[0]-=1\n",
    "                        else:break\n",
    "            ans = max(ans, pos[0]*pos[0]+pos[1]*pos[1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        direction = {'up':[0,1,'left','right'],\n",
    "                    'down':[0,-1,'right','left'],\n",
    "                    'left':[-1,0,'down','up'],\n",
    "                    'right':[1,0,'up','down']}\n",
    "        x,y = 0,0\n",
    "        dir = 'up'\n",
    "        res = 0\n",
    "        obstacles = set(map(tuple,obstacles))\n",
    "        for command in commands:\n",
    "            if command > 0:\n",
    "                for step in range(command):\n",
    "                    if (x+direction[dir][0],y+direction[dir][1]) not in obstacles:\n",
    "                        x  += direction[dir][0]\n",
    "                        y += direction[dir][1]\n",
    "                        res = max(res, x**2+y**2)\n",
    "                    else:\n",
    "                        break\n",
    "            else:\n",
    "                if command == -1:\n",
    "                    dir = direction[dir][3]\n",
    "                else:\n",
    "                    dir = direction[dir][2]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        n = len(commands)\n",
    "        m = len(obstacles)\n",
    "        c, d = [], []\n",
    "        a = 10000\n",
    "        p = [0,0]\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            c.append(obstacles[i][0])\n",
    "            d.append(obstacles[i][1])\n",
    "        for i in range(n):\n",
    "            k = -1\n",
    "            if commands[i] == -1:\n",
    "                a += 1\n",
    "                continue\n",
    "            elif commands[i] == -2:\n",
    "                a -= 1\n",
    "                continue\n",
    "            if a % 4 == 0:\n",
    "                while p[0] in c[k+1:]:\n",
    "                    k = c[k+1:].index(p[0]) + k + 1\n",
    "                    if commands[i] + p[1] >= d[k] and d[k] > p[1]:\n",
    "                        p[1] = d[k] - 1\n",
    "                        break\n",
    "                else:\n",
    "                    p[1] += commands[i]\n",
    "            elif a % 4 == 1:\n",
    "                while p[1] in d[k+1:]:\n",
    "                    k = d[k+1:].index(p[1]) + k + 1\n",
    "                    if commands[i] + p[0] >= c[k] and c[k] > p[0]:\n",
    "                        p[0] = c[k] - 1\n",
    "                        break\n",
    "                else:\n",
    "                    p[0] += commands[i]\n",
    "            elif a % 4 == 2:\n",
    "                while p[0] in c[k+1:]:\n",
    "                    k = c[k+1:].index(p[0]) + k + 1\n",
    "                    if p[1] - commands[i] <= d[k] and d[k] < p[1]:\n",
    "                        p[1] = d[k] + 1\n",
    "                        break\n",
    "                else:\n",
    "                    p[1] -= commands[i]        \n",
    "            elif a % 4 == 3:\n",
    "                while p[1] in d[k+1:]:\n",
    "                    k = d[k+1:].index(p[1]) + k + 1\n",
    "                    if p[0] - commands[i] <= c[k] and c[k] < p[0]:\n",
    "                        p[0] = c[k] + 1\n",
    "                        break\n",
    "                else:\n",
    "                    p[0] -= commands[i]\n",
    "            ans = max(ans,p[0]**2 + p[1]**2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        # return [1,2] in obstacles\n",
    "        obstacles.sort(key = lambda x:(x[0],x[1]))\n",
    "        n=len(obstacles)\n",
    "        def check(x,y):\n",
    "            if n==0:return True\n",
    "            l,r=0,n-1\n",
    "            while l<r:\n",
    "                mid=(r-l)//2+l \n",
    "                if obstacles[mid][0]>=x:\n",
    "                    r=mid \n",
    "                else:\n",
    "                    l=mid+1\n",
    "            if obstacles[l][0]!=x:\n",
    "                return True\n",
    "            # l,r=0,n-1\n",
    "            r=l \n",
    "            while r<n and obstacles[r][0]==x:\n",
    "                r+=1\n",
    "            r-=1\n",
    "\n",
    "            while l<r:\n",
    "                mid=(r-l)//2+l \n",
    "                if obstacles[mid][1]>=y:\n",
    "                    r=mid \n",
    "                else:\n",
    "                    l=mid+1\n",
    "            if obstacles[l][1]!=y:\n",
    "                return True\n",
    "            return False\n",
    "        # print(check(2,4))\n",
    "        direction=[[0,1],[1,0],[0,-1],[-1,0]]\n",
    "        curd=0\n",
    "        x,y=0,0\n",
    "        ans=0\n",
    "        # flag=False\n",
    "        temp=list()\n",
    "        for cmd in commands:\n",
    "            if cmd<0:\n",
    "                # while flag and [x,y] in obstacles :\n",
    "                #     x-=direction[curd][0]\n",
    "                #     y-=direction[curd][1]\n",
    "                if cmd==-1:\n",
    "                    curd=(curd+1)%4\n",
    "                else:\n",
    "                    curd=(curd+3)%4\n",
    "                continue\n",
    "            #temp.append(check(x+direction[curd][0],y+direction[curd][1]))\n",
    "            while cmd>0 and check(x+direction[curd][0],y+direction[curd][1]):\n",
    "                x+=direction[curd][0]\n",
    "                y+=direction[curd][1]\n",
    "                cmd-=1\n",
    "            ans=max(ans,x**2+y**2)\n",
    "            #temp.append(check(x+direction[curd][0],y+direction[curd][1]))\n",
    "        # print(temp)\n",
    "        # print(obstacles)\n",
    "        # print(check(0,1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        # map = {}\n",
    "        # #for i in range(len(obstacles)):\n",
    "        #     #map[(obstacles[i][0], obstacles[i][1])] = 1;\n",
    "        # #print(map)\n",
    "        # maxm = -1\n",
    "        # direction = 0\n",
    "        # pos = (0,0)\n",
    "        # for i in commands:\n",
    "        #     if i == -1:\n",
    "        #         direction = (direction + 1) % 4\n",
    "        #     elif i == -2:\n",
    "        #         direction = (direction + 3) % 4\n",
    "        #     else:\n",
    "        #         if direction == 0:\n",
    "        #             pos = (pos[0], pos[1]+i)\n",
    "        #             for j in obstacles:\n",
    "        #                 if j[0] == pos[0] and j[1] <= pos[1]:\n",
    "        #                     pos = (pos[0], j[1]-1)\n",
    "        #                     break\n",
    "        #                     #print(\"ops\")\n",
    "        #         if direction == 1:\n",
    "        #             pos = (pos[0]+i, pos[1])\n",
    "        #             for j in obstacles:\n",
    "        #                 if j[0] <= pos[0] and j[1] == pos[1]:\n",
    "        #                     pos = (j[0]-1, pos[1])\n",
    "        #                     break\n",
    "        #                     #print(\"ops\")\n",
    "        #         if direction == 2:\n",
    "        #             pos = (pos[0], pos[1]-i)\n",
    "        #             for j in obstacles:\n",
    "        #                 if j[0] == pos[0] and j[1] >= pos[1]:\n",
    "        #                     pos = (pos[0], j[1]+1)\n",
    "        #                     break\n",
    "        #                     #print(\"ops\")\n",
    "        #         if direction == 3:\n",
    "        #             pos = (pos[0]-i, pos[1])\n",
    "        #             for j in obstacles:\n",
    "        #                 if j[0] >= pos[0] and j[1] == pos[1]:\n",
    "        #                     pos = (j[0]+1, pos[1])\n",
    "        #                     break\n",
    "        #                     #print(\"ops\")\n",
    "        #         #print(pos)\n",
    "        #         distance = pos[0]**2 + pos[1]**2\n",
    "        #         if distance > maxm:\n",
    "        #             maxm = distance\n",
    "        # #distance = pos[0]**2 + pos[1]**2\n",
    "        # return maxm\n",
    "        flag = 0\n",
    "        x = y = 0\n",
    "        res = 0\n",
    "        d = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n",
    "        dx = d[flag][0]\n",
    "        dy = d[flag][1]\n",
    "        obstacles = {tuple(obstacle) for obstacle in obstacles}\n",
    "        for cmd in commands:\n",
    "            if cmd == -1:\n",
    "                flag += 1\n",
    "                dx = d[flag % 4][0]\n",
    "                dy = d[flag % 4][1]\n",
    "            elif cmd == -2:\n",
    "                flag  += 3\n",
    "                dx = d[flag % 4][0]\n",
    "                dy = d[flag % 4][1]            \n",
    "            else:\n",
    "                for i in range(cmd):\n",
    "                    x += dx\n",
    "                    y += dy\n",
    "                    if (x, y) in obstacles:\n",
    "                        x -= dx\n",
    "                        y -= dy\n",
    "                        break\n",
    "            res = max(res, x*x+y*y)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "DIRS = ((0, 1), (1, 0), (0, -1), (-1, 0)) \n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        ans = d = x = y = 0\n",
    "        obstacles = set((u, v) for u, v in obstacles)\n",
    "        for c in commands:\n",
    "            if c == -1:\n",
    "                d = (d + 1) % 4\n",
    "            elif c == -2:\n",
    "                d = (d + -1) % 4\n",
    "            else:\n",
    "                for _ in range(c):\n",
    "                    x += DIRS[d][0]\n",
    "                    y += DIRS[d][1]\n",
    "                    if (x, y) in obstacles:\n",
    "                        x -= DIRS[d][0]\n",
    "                        y -= DIRS[d][1]\n",
    "                        break\n",
    "            ans = max(ans, x * x + y * y)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        d = 'N'\n",
    "        ds = ['N', 'E', 'S', 'W']\n",
    "\n",
    "        def change_d(cur_d, turn):\n",
    "            idx = -1\n",
    "            for i in range(4):\n",
    "                if cur_d == ds[i]:\n",
    "                    idx = i\n",
    "                    break\n",
    "            if turn == -1:\n",
    "                return ds[(idx + 1) % 4]\n",
    "            else:\n",
    "                return ds[(idx + 3) % 4]\n",
    "            \n",
    "        ans = 0\n",
    "        ob_set = set()\n",
    "        for x, y in obstacles:\n",
    "            ob_set.add((x, y))\n",
    "        x, y = 0, 0\n",
    "        for c in commands:\n",
    "            if c < 0:\n",
    "                d = change_d(d, c)\n",
    "            else:\n",
    "                for i in range(c):\n",
    "                    if d == 'N':\n",
    "                        y += 1\n",
    "                        if (x, y) in ob_set:\n",
    "                            y -= 1\n",
    "                            break\n",
    "                    elif d == 'E':\n",
    "                        x += 1\n",
    "                        if (x, y) in ob_set:\n",
    "                            x -= 1\n",
    "                            break\n",
    "                    elif d == 'S':\n",
    "                        y -= 1\n",
    "                        if (x, y) in ob_set:\n",
    "                            y += 1\n",
    "                            break\n",
    "                    else:\n",
    "                        x -= 1\n",
    "                        if (x, y) in ob_set:\n",
    "                            x += 1\n",
    "                            break\n",
    "                    ans = max(ans, x ** 2 + y ** 2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        dirs = (0, 1, 0, -1, 0)\n",
    "        s = {(x, y) for x, y in obstacles}\n",
    "        ans = k = 0\n",
    "        x = y = 0\n",
    "        for c in commands:\n",
    "            if c == -2:\n",
    "                k = (k + 3) % 4\n",
    "            elif c == -1:\n",
    "                k = (k + 1) % 4\n",
    "            else:\n",
    "                for _ in range(c):\n",
    "                    nx, ny = x + dirs[k], y + dirs[k + 1]\n",
    "                    if (nx, ny) in s:\n",
    "                        break\n",
    "                    x, y = nx, ny\n",
    "                    ans = max(ans, x * x + y * y)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        dir_list = ((0, 1), (1, 0), (0, -1), (-1, 0))\n",
    "        x, y = 0, 0\n",
    "        dir = 0\n",
    "        obstacles = set(tuple(o) for o in obstacles)\n",
    "        for com in commands:\n",
    "            if com < 0:\n",
    "                gap = 1 if com == -1 else -1\n",
    "                dir = (dir + gap + len(dir_list)) % len(dir_list)\n",
    "            else:\n",
    "                for i in range(com):\n",
    "                    if tuple([x + dir_list[dir][0], y + dir_list[dir][1]]) in obstacles:\n",
    "                        break\n",
    "                    x += dir_list[dir][0]\n",
    "                    y += dir_list[dir][1]\n",
    "                    ans = max(ans, x ** 2 + y ** 2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        new_commands = [commands[0]]\n",
    "        for i in range(1, len(commands)):\n",
    "            if commands[i] > 0 and new_commands[-1] > 0:\n",
    "                new_commands[-1] += commands[i]\n",
    "            else:\n",
    "                new_commands.append(commands[i])\n",
    "        commands = new_commands\n",
    "        import math\n",
    "        direction = 90\n",
    "        x, y = 0, 0\n",
    "        res = 0\n",
    "        for command in commands:\n",
    "            if command == -1:\n",
    "                direction -= 90\n",
    "            elif command == -2:\n",
    "                direction += 90\n",
    "            else:\n",
    "                x_next = x + command * int(math.cos(math.radians(direction)))\n",
    "                y_next = y + command * int(math.sin(math.radians(direction)))\n",
    "                \n",
    "                \n",
    "                x_intervals = [x, x_next] if x_next >= x else [x_next, x]\n",
    "                y_intervals = [y, y_next] if y_next >= y else [y_next, y]\n",
    "\n",
    "                abs_dist = command\n",
    "                for obstacle_x, obstacle_y in obstacles:\n",
    "                    if obstacle_x == x and obstacle_y == y:\n",
    "                        continue\n",
    "                    if x_intervals[0] <= obstacle_x <= x_intervals[1] and y_intervals[0] <= obstacle_y <= y_intervals[1]:\n",
    "                        new_dist = abs(obstacle_x - x + obstacle_y - y)-1\n",
    "                        if new_dist < abs_dist:\n",
    "                            x_next = obstacle_x - int(math.cos(math.radians(direction)))\n",
    "                            y_next = obstacle_y - int(math.sin(math.radians(direction)))\n",
    "\n",
    "                            x_intervals = [x, x_next] if x_next >= x else [x_next, x]\n",
    "                            y_intervals = [y, y_next] if y_next >= y else [y_next, y]\n",
    "                # print(command, x_next, y_next)\n",
    "                x = x_next\n",
    "                y = y_next\n",
    "                \n",
    "                res = max(res, x**2 + y**2)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        # 0 北 东 南 西\n",
    "        dic = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        obs = dict()\n",
    "        for x, y in obstacles:\n",
    "            obs[(x,y)] = 1\n",
    "        x = 0\n",
    "        y = 0\n",
    "        cnt = 0\n",
    "        ans = 0\n",
    "        for c in commands:\n",
    "            if c == -2:\n",
    "                    cnt = (cnt + 3) % 4\n",
    "            elif c == -1:\n",
    "                cnt = (cnt + 1) % 4\n",
    "            else:\n",
    "                # nx =  x + c * dic[cnt][0]\n",
    "                # ny =  y + c * dic[cnt][1]\n",
    "                for i in range(0, c):\n",
    "                    nx =  x + dic[cnt][0]\n",
    "                    ny =  y + dic[cnt][1] \n",
    "                    if (nx, ny) in obs.keys():\n",
    "                        break\n",
    "                    x = nx\n",
    "                    y = ny \n",
    "                ans = max(x * x + y * y, ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        dirs = [[-1,0],[0,1],[1,0],[0,-1]]\n",
    "        mp = set(tuple(i) for i in obstacles)\n",
    "        px,py,d = 0,0,1\n",
    "        res = 0\n",
    "        for c in commands:\n",
    "            if c < 0:\n",
    "                d = (d + 1) if c == -1 else (d - 1) \n",
    "                d %= 4\n",
    "            else:\n",
    "                for i in range(c):\n",
    "                    if tuple([px + dirs[d][0], py + dirs[d][1]]) in mp:\n",
    "                        break\n",
    "                    px += dirs[d][0]\n",
    "                    py += dirs[d][1]\n",
    "                    res = max(res,px*px + py*py)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        dx,dy = [0,1,0,-1,1,-1,1,-1],[1,0,-1,0,-1,-1,1,1]\n",
    "        res = 0\n",
    "        s = set((x,y) for x, y in obstacles)\n",
    "        cur = 0\n",
    "        pos_x,pos_y = 0, 0\n",
    "        for command in commands:\n",
    "            if command == -1:\n",
    "                cur = (cur+1)%4\n",
    "            elif command == -2:\n",
    "                cur = (cur-1)%4\n",
    "            else:\n",
    "                x,y = dx[cur],dy[cur]\n",
    "                while command:\n",
    "                    if(pos_x+x,pos_y+y) in s:\n",
    "                        break\n",
    "                    pos_x,pos_y = pos_x+x,pos_y+y\n",
    "                    res = max(res,pos_x**2+pos_y**2)\n",
    "                    command -= 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        x=y=0\n",
    "        DirectY = 1\n",
    "        DirectX = 0\n",
    "        res = 0\n",
    "        dic = {}\n",
    "        for a,b in obstacles:\n",
    "            dic[(a,b)]=0\n",
    "\n",
    "        for command in commands:\n",
    "            if 1<=command<=9:\n",
    "                newX = x + DirectX*command\n",
    "                newY = y + DirectY*command\n",
    "\n",
    "                if DirectX:\n",
    "                    for tempX in range(x+DirectX, newX+DirectX, DirectX):\n",
    "                        if (tempX, y) in dic:\n",
    "                            newX = tempX-DirectX\n",
    "                            break\n",
    "                if DirectY:\n",
    "                    for tempY in range(y+DirectY, newY+DirectY, DirectY):\n",
    "                        if (x, tempY) in dic:\n",
    "                            newY = tempY-DirectY\n",
    "                            break\n",
    "                x = newX\n",
    "                y = newY\n",
    "                res = max(res, pow(x,2)+pow(y,2))\n",
    "            elif command == -1:\n",
    "                if DirectX == 1:\n",
    "                    DirectX = 0\n",
    "                    DirectY = -1\n",
    "                elif DirectX == -1:\n",
    "                    DirectX = 0\n",
    "                    DirectY = 1\n",
    "                elif DirectY == 1:\n",
    "                    DirectY = 0\n",
    "                    DirectX = 1\n",
    "                elif DirectY == -1:\n",
    "                    DirectY = 0\n",
    "                    DirectX = -1\n",
    "            elif command == -2:\n",
    "                if DirectX == 1:\n",
    "                    DirectX = 0\n",
    "                    DirectY = 1\n",
    "                elif DirectX == -1:\n",
    "                    DirectX = 0\n",
    "                    DirectY = -1\n",
    "                elif DirectY == 1:\n",
    "                    DirectY = 0\n",
    "                    DirectX = -1\n",
    "                elif DirectY == -1:\n",
    "                    DirectY = 0\n",
    "                    DirectX = 1\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        obset=set()\n",
    "        d=[[0,1],[1,0],[0,-1],[-1,0]]\n",
    "        for i in obstacles:\n",
    "            obset.add(tuple(i))\n",
    "        x,y,fx,res=0,0,0,0\n",
    "        for i in commands:\n",
    "            if i==-2:\n",
    "                fx=(fx-1)%4\n",
    "            elif i==-1:\n",
    "                fx=(fx+1)%4\n",
    "            else:\n",
    "                for j in range(i):\n",
    "                    if (x+d[fx][0],y+d[fx][1]) in obset:\n",
    "                        break\n",
    "                    x,y=x+d[fx][0],y+d[fx][1]\n",
    "                res=max(res,x**2+y**2)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        dirts = [[-1,0],[0,1],[1,0],[0,-1]]\n",
    "        res,px,py,d = 0 , 0 , 0 , 1\n",
    "        mp = set(tuple(i) for i in obstacles)\n",
    "        for i in commands:\n",
    "            if i < 0 :\n",
    "                if i == -1:\n",
    "                    d += 1\n",
    "                else:\n",
    "                    d -= 1\n",
    "                d %= 4\n",
    "            else:\n",
    "                for c in range(i):\n",
    "                    if tuple([px+dirts[d][0],py+dirts[d][1]]) in mp:\n",
    "                        break\n",
    "                    px,py = px+dirts[d][0],py+dirts[d][1]\n",
    "                    res = max(res,px*px+py*py)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]]\n",
    "        x,y,t = 0,0,1\n",
    "        res = 0\n",
    "        obstacles = set([tuple(i) for i in obstacles])\n",
    "        for c in commands:\n",
    "            if c == -2:\n",
    "                t-=1\n",
    "                t%=4\n",
    "            elif c == -1:\n",
    "                t+=1\n",
    "                t%=4\n",
    "            else:\n",
    "                for i in range(c):\n",
    "                    target = (x + dirs[t][0], y + dirs[t][1])\n",
    "                    if target in obstacles:\n",
    "                        break\n",
    "                    x,y = target\n",
    "                    res = max(res, x**2 + y**2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        #0-北，1-东，2-南，3-西\n",
    "        direction=0\n",
    "        dx=[0,1,0,-1]\n",
    "        dy=[1,0,-1,0]\n",
    "        x=y=0\n",
    "        res=0\n",
    "        obstaclesSet={tuple(o) for o in obstacles}\n",
    "        for com in commands:\n",
    "            if com==-1:\n",
    "                if direction==3:\n",
    "                    direction=0\n",
    "                else:\n",
    "                    direction+=1\n",
    "            elif com==-2:\n",
    "                if direction==0:\n",
    "                    direction=3\n",
    "                else:\n",
    "                    direction-=1\n",
    "            else:\n",
    "                for i in range(com):\n",
    "                    temp=[x+dx[direction],y+dy[direction]]\n",
    "                    if not (x+dx[direction],y+dy[direction]) in obstaclesSet:\n",
    "                        x=x+dx[direction]\n",
    "                        y=y+dy[direction]\n",
    "                        res=max(res,x*x+y*y)\n",
    "                    print('cur:',x,y)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        obstacleSet = set(map(tuple, obstacles))\n",
    "        d = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n",
    "        res = x = y = dirc = 0\n",
    "        for op in commands:\n",
    "            if op == -1:\n",
    "                dirc = (dirc + 1) % 4\n",
    "            elif op == -2:\n",
    "                dirc = (dirc - 1) % 4\n",
    "            else:\n",
    "                for _ in range(op):\n",
    "                    nx, ny = x + d[dirc][0], y + d[dirc][1]\n",
    "                    if (nx, ny) not in obstacleSet:\n",
    "                        x, y = nx, ny\n",
    "                        res = max(res, nx * nx + ny * ny)\n",
    "                    else:\n",
    "                        break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        # 初始化结果\n",
    "        result = 0\n",
    "        \n",
    "        # 从原点（ 0 ，0 ）位置开始出发\n",
    "        x = 0\n",
    "\n",
    "        y = 0\n",
    "        \n",
    "        # 机器人前进的方向\n",
    "        # 初始方向：正北\n",
    "        # 0 表示 向北\n",
    "        # 1 表示 向东\n",
    "        # 2 表示 向南\n",
    "        # 3 表示 向西\n",
    "        direction = 0\n",
    "\n",
    "        # 定义四个方向\n",
    "        dx = [0, 1, 0, -1]\n",
    "\n",
    "        dy = [1, 0, -1, 0]\n",
    "\n",
    "        # 障碍物有多个，所以需要有一个障碍物坐标点集合\n",
    "        # 使用 集合 Set 存储障碍物的坐标，用来检查下一步是否受阻\n",
    "        # 机器人每试图走一个位置，就用此位置与障碍物集合列表里的坐标进行比较，看是否刚好是障碍物坐标点\n",
    "        obstacleSet = set(map(tuple, obstacles))\n",
    "\n",
    "        # 机器人开始行走\n",
    "        for com in commands : \n",
    "\n",
    "            # -2：向左转 90 度\n",
    "            if com == -2 :\n",
    "                # 1、当前方向为正北方向，即 direction == 0 ，向左转 90 度\n",
    "                # 来到 向西 方向，即 direction 需要更新为 3\n",
    "                # 2、当前方向【不是】正北方向，即 direction ！= 0 ，向左转 90 度\n",
    "                # 西 -> 南，即 3 -> 2\n",
    "                # 南 -> 东，即 2 -> 1\n",
    "                # 东 -> 北，即 1 -> 0\n",
    "                # 即 direction 需要更新为 direction - 1 \n",
    "                if direction == 0:\n",
    "                    direction = 3\n",
    "                else:\n",
    "                    direction = direction - 1\n",
    "                # direction = (direction == 0) ? 3 : direction - 1\n",
    "\n",
    "            # -1：向右转 90 度\n",
    "            elif com == -1 :\n",
    "                # 1、当前方向为正西方向，即 direction == 3 ，向右转 90 度\n",
    "                # 来到 向北 方向，即 direction 需要更新为 0\n",
    "                # 2、当前方向【不是】正西方向，即 direction ！= 3 ，向右转 90 度\n",
    "                # 北 -> 东，即 0 -> 1\n",
    "                # 东 -> 南，即 1 -> 2\n",
    "                # 南 -> 西，即 2 -> 3\n",
    "                # 即 direction 需要更新为 direction + 1 \n",
    "                if direction == 3:\n",
    "                    direction = 0\n",
    "                else:\n",
    "                    direction = direction + 1\n",
    "                # direction = (direction == 3) ? 0 : direction + 1\n",
    "            \n",
    "            # 1 <= x <= 9 ：向前移动 x 个单位长度\n",
    "            else :\n",
    "                # 没有遇到障碍物，一直往前走 com 个单位长度\n",
    "                for k in range(com):\n",
    "                    if (x+dx[direction], y+dy[direction]) not in obstacleSet:\n",
    "                        x += dx[direction]\n",
    "                        y += dy[direction]\n",
    "                        result = max(result, x*x + y*y)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n",
    "        d = 0\n",
    "\n",
    "        ans = 0\n",
    "        obs = set()\n",
    "        for x, y in obstacles:\n",
    "            obs.add((x, y))\n",
    "\n",
    "        px, py = 0, 0\n",
    "        for c in commands:\n",
    "            if c == -1:\n",
    "                d = (d + 1) % 4\n",
    "            elif c == -2:\n",
    "                d = (d + 3) % 4\n",
    "            else:\n",
    "                for _ in range(c):\n",
    "                    nx, ny = px + dirs[d][0], py + dirs[d][1]\n",
    "                    if (nx, ny) in obs:\n",
    "                        break\n",
    "                    px, py = nx, ny\n",
    "                    ans = max(ans, nx ** 2 + ny **2)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        dirs = (0,1,0,-1,0) #表示方向\n",
    "        s={(x,y) for x,y in obstacles}\n",
    "        ans=k=0\n",
    "        x=y=0\n",
    "        for c in commands:\n",
    "            if c == -2:\n",
    "                k = (k+3)%4\n",
    "            if c == -1:\n",
    "                k = (k+1)%4\n",
    "            else:\n",
    "                for _ in range(c):\n",
    "                    nx,ny=x+dirs[k], y+dirs[k+1]\n",
    "                    if (nx,ny) in s:\n",
    "                        break\n",
    "                    x,y=nx,ny\n",
    "                    ans = max(ans,x*x+y*y)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        dirs = (0, 1, 0, -1, 0)\n",
    "        s = {(x, y) for x, y in obstacles}\n",
    "        ans = k = 0\n",
    "        x = y = 0\n",
    "        for c in commands:\n",
    "            if c == -2:\n",
    "                k = (k + 3) % 4\n",
    "            elif c == -1:\n",
    "                k = (k + 1) % 4\n",
    "            else:\n",
    "                for _ in range(c):\n",
    "                    nx, ny = x + dirs[k], y + dirs[k + 1]\n",
    "                    if (nx, ny) in s:\n",
    "                        break\n",
    "                    x, y = nx, ny\n",
    "                    ans = max(ans, x * x + y * y)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        dirs = (0, 1, 0, -1, 0)\n",
    "        s = {(x, y) for x, y in obstacles}\n",
    "        ans = k = 0\n",
    "        x = y = 0\n",
    "        for c in commands:\n",
    "            if c == -2:\n",
    "                k = (k + 3) % 4\n",
    "            elif c == -1:\n",
    "                k = (k + 1) % 4\n",
    "            else:\n",
    "                for _ in range(c):\n",
    "                    nx, ny = x + dirs[k], y + dirs[k + 1]\n",
    "                    if (nx, ny) in s:\n",
    "                        break\n",
    "                    x, y = nx, ny\n",
    "                    ans = max(ans, x * x + y * y)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "\n",
    "        dy =[1,0,-1,0]\n",
    "        dx= [0,1,0,-1]\n",
    "        s = {(x,y)for x,y in obstacles}\n",
    "        ans = m = 0\n",
    "        x = y = 0\n",
    "        for c in commands:\n",
    "            if c== -2 :\n",
    "                m = (m+3)%4\n",
    "            elif c == -1 :\n",
    "                m = (m+1)%4\n",
    "            else :\n",
    "                for _ in range(c):\n",
    "                    nx, ny = x + dx[m], y + dy[m]\n",
    "                    if (nx, ny) in s:\n",
    "                        break\n",
    "                    x, y = nx, ny\n",
    "                    ans = max(ans, x * x + y * y)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        x, y, dx, dy, res = 0, 0, 0, 1, 0\n",
    "        obstacles = set(map(tuple, obstacles))\n",
    "        for cmd in commands:\n",
    "            if cmd == -2:\n",
    "                dx, dy = -dy, dx\n",
    "            elif cmd == -1:\n",
    "                dx, dy = dy, -dx\n",
    "            else:\n",
    "                for _ in range(cmd):\n",
    "                    if (x + dx, y + dy) in obstacles:\n",
    "                        break\n",
    "                    x += dx\n",
    "                    y += dy\n",
    "                    res = max(res, x * x + y * y)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        dirs = [(1, 0), (0, -1), (-1, 0), (0, 1)]\n",
    "        p = [0, 0]\n",
    "        d = 3\n",
    "        obs = set(map(tuple, obstacles))\n",
    "        ans = 0\n",
    "        for c in commands:\n",
    "            if c == -1:\n",
    "                d = (d + 1) % 4\n",
    "            elif c == -2:\n",
    "                d = (d - 1) % 4\n",
    "            else:\n",
    "                dx, dy = dirs[d] \n",
    "                for _ in range(c):\n",
    "                    if (p[0] + dx, p[1] + dy) not in obs:\n",
    "                        p[0] += dx\n",
    "                        p[1] += dy\n",
    "                    else:\n",
    "                        break\n",
    "            ans = max(ans, abs(p[0]) ** 2 + abs(p[1]) ** 2 )\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]]\n",
    "        px, py, d = 0, 0, 1\n",
    "        mp = set([tuple(i) for i in obstacles])\n",
    "        res = 0\n",
    "        for c in commands:\n",
    "            if c < 0:\n",
    "                d += 1 if c == -1 else -1\n",
    "                d %= 4\n",
    "            else:\n",
    "                for i in range(c):\n",
    "                    if tuple([px + dirs[d][0], py + dirs[d][1]]) in mp:\n",
    "                        break\n",
    "                    px, py = px + dirs[d][0], py + dirs[d][1]\n",
    "                    res = max(res, px * px + py * py)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        # 返回的是机器人距离原点的欧式距离的平方\n",
    "        # 含有障碍物\n",
    "        # 原点可能会有障碍物\n",
    "\n",
    "        # 先纯模拟一下看看什么情况\n",
    "        # 0,初始方向,1，初始向左转,2,初始向右转，3,初始反方向\n",
    "        dirs = [(0,1),(1,0),(0,-1),(-1,0),(0,1)]\n",
    "        dirn = [(0,1),(-1,0),(0,-1),(1,0),(0,1)]\n",
    "        def nxtdir(i,j,c):\n",
    "            if 1 <= c <=9:\n",
    "                return i,j\n",
    "            if c == -1:\n",
    "                for nxt in range(len(dirs)):\n",
    "                    if (i,j) == dirs[nxt]:\n",
    "                        return dirs[nxt+1]\n",
    "            if c == -2:\n",
    "                for nxt in range(len(dirn)):\n",
    "                    if (i,j) == dirn[nxt]:\n",
    "                        return dirn[nxt+1]\n",
    "        obs = set([(i,j) for i,j in obstacles])\n",
    "        nxtd = (0,1)\n",
    "        res = 0 \n",
    "        i,j = (0,0)\n",
    "        for c in commands:\n",
    "            if 1 <= c <=9:\n",
    "                # 在nxtd方向上走转移(i，j)\n",
    "                m = nxtd[0]\n",
    "                n = nxtd[1]\n",
    "                for step in range(1,c+1):\n",
    "                    i += m\n",
    "                    j += n\n",
    "                    if (i,j) in obs:\n",
    "                        i -= m\n",
    "                        j -= n\n",
    "                        break \n",
    "                # print(i,j)\n",
    "                res = max(i**2+j**2,res)\n",
    "            nxtd = nxtdir(nxtd[0],nxtd[1],c)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\r\n",
    "        flag = 0\r\n",
    "        xy = [0, 0]\r\n",
    "        s = set()\r\n",
    "        ans = 0\r\n",
    "        for x, y in obstacles:\r\n",
    "            s.add((x, y))\r\n",
    "\r\n",
    "        for v in commands:\r\n",
    "            if flag == 0:\r\n",
    "                for i in range(v):\r\n",
    "                    if (xy[0], xy[1] + 1) not in s:\r\n",
    "                        xy[1] += 1\r\n",
    "                    else:\r\n",
    "                        break\r\n",
    "            elif flag == 1:\r\n",
    "                for i in range(v):\r\n",
    "                    if (xy[0] + 1, xy[1]) not in s:\r\n",
    "                        xy[0] += 1\r\n",
    "                    else:\r\n",
    "                        break\r\n",
    "            elif flag == 2:\r\n",
    "                for i in range(v):\r\n",
    "                    if (xy[0], xy[1] - 1) not in s:\r\n",
    "                        xy[1] -= 1\r\n",
    "                    else:\r\n",
    "                        break\r\n",
    "            else:\r\n",
    "                for i in range(v):\r\n",
    "                    if (xy[0] - 1, xy[1]) not in s:\r\n",
    "                        xy[0] -= 1\r\n",
    "                    else:\r\n",
    "                        break\r\n",
    "            ans = max(ans, xy[0] ** 2 + xy[1] ** 2)\r\n",
    "\r\n",
    "            if v == -1:\r\n",
    "                flag += 1\r\n",
    "                if flag > 3:\r\n",
    "                    flag -= 4\r\n",
    "            elif v == -2:\r\n",
    "                flag -= 1\r\n",
    "                if flag < 0:\r\n",
    "                    flag += 4\r\n",
    "\r\n",
    "        return(ans)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        dirs = [0, 1, 0, -1, 0]\n",
    "        obstacles = {(a, b) for a, b in obstacles}\n",
    "        ans = k = x = y = 0\n",
    "        for c in commands:\n",
    "            if c == -1:\n",
    "                k = (k + 1) % 4\n",
    "            elif c == -2:\n",
    "                k = (k + 3) % 4\n",
    "            else:\n",
    "                for _ in range(c):\n",
    "                    nx, ny = x + dirs[k], y + dirs[k + 1]\n",
    "                    if (nx, ny) in obstacles:\n",
    "                        break\n",
    "                    x, y, = nx, ny\n",
    "                    ans = max(ans, x * x + y * y)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        dirs = (0, 1, 0, -1, 0)\n",
    "        s = {(x, y) for x, y in obstacles}\n",
    "        ans = k = 0\n",
    "        x = y = 0\n",
    "        for c in commands:\n",
    "            if c == -2:\n",
    "                k = (k + 3) % 4\n",
    "            elif c == -1:\n",
    "                k = (k + 1) % 4\n",
    "            else:\n",
    "                for _ in range(c):\n",
    "                    nx, ny = x + dirs[k], y + dirs[k + 1]\n",
    "                    if (nx, ny) in s:\n",
    "                        break\n",
    "                    x, y = nx, ny\n",
    "                    ans = max(ans, x * x + y * y)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "\n",
    "        dy =[1,0,-1,0]\n",
    "        dx= [0,1,0,-1]\n",
    "        s = {(x,y)for x,y in obstacles}\n",
    "        ans = m = 0\n",
    "        x = y = 0\n",
    "        for c in commands:\n",
    "            if c== -2 :\n",
    "                m = (m+3)%4\n",
    "            elif c == -1 :\n",
    "                m = (m+1)%4\n",
    "            else :\n",
    "                for _ in range(c):\n",
    "                    nx, ny = x + dx[m], y + dy[m]\n",
    "                    if (nx, ny) in s:\n",
    "                        break\n",
    "                    x, y = nx, ny\n",
    "                    ans = max(ans, x * x + y * y)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        obstacles_set = set([tuple(obstacle) for obstacle in obstacles])\n",
    "        x, y = 0, 0\n",
    "        dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]\n",
    "        d = 1\n",
    "        for command in commands:\n",
    "            if command == -2:\n",
    "                d = (d + 3) % 4\n",
    "            elif command == -1:\n",
    "                d = (d + 1) % 4\n",
    "            else:\n",
    "                for _ in range(command):\n",
    "                    new_x, new_y = x + dirs[d][0], y + dirs[d][1]\n",
    "                    if (new_x, new_y) in obstacles_set:\n",
    "                        break\n",
    "                    x, y = new_x, new_y\n",
    "                    res = max(res, x**2 + y**2)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        result = 0\n",
    "\n",
    "        direction = 0\n",
    "\n",
    "        x = 0\n",
    "        y = 0\n",
    "\n",
    "        dx = [0, 1, 0, -1]\n",
    "        dy = [1, 0, -1, 0]\n",
    "\n",
    "        obstacleSet = set(map(tuple, obstacles))\n",
    "\n",
    "        for com in commands:\n",
    "\n",
    "            if com == -2:\n",
    "                if direction == 0:\n",
    "                    direction = 3\n",
    "                else:\n",
    "                    direction = direction - 1\n",
    "            \n",
    "            elif com == -1:\n",
    "                if direction == 3:\n",
    "                    direction = 0\n",
    "                else:\n",
    "                    direction = direction + 1\n",
    "            \n",
    "            else:\n",
    "                for i in range(com):\n",
    "                    if (x+dx[direction], y+dy[direction]) not in obstacleSet:\n",
    "                        x += dx[direction]\n",
    "                        y += dy[direction]\n",
    "                        result = max(result, x*x+y*y)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\r\n",
    "        invalid_set=set(map(tuple,obstacles))\r\n",
    "        # if (0,0) in invalid_set:\r\n",
    "        #     return 0\r\n",
    "        dirs=[\r\n",
    "            [0,1],\r\n",
    "            [1,0],\r\n",
    "            [0,-1],\r\n",
    "            [-1,0]\r\n",
    "        ]\r\n",
    "        dir_idx=0\r\n",
    "        pos=[0,0]\r\n",
    "        ret=0\r\n",
    "        for cmd in commands:\r\n",
    "            if cmd==-2:\r\n",
    "                dir_idx=(dir_idx-1)%4\r\n",
    "            elif cmd==-1:\r\n",
    "                dir_idx=(dir_idx+1)%4\r\n",
    "            else:\r\n",
    "                copy_x,copy_y=pos\r\n",
    "                dir_x,dir_y=dirs[dir_idx]\r\n",
    "                for i in range(cmd):\r\n",
    "                    nxt=[0,0]\r\n",
    "                    nxt[0]=pos[0]+dir_x\r\n",
    "                    nxt[1]=pos[1]+dir_y\r\n",
    "                    if tuple(nxt) in invalid_set:\r\n",
    "                        break\r\n",
    "                    pos=nxt\r\n",
    "                    if abs(pos[0])>abs(copy_x) or abs(pos[1])>abs(copy_y):\r\n",
    "                        ret=max(ret,pos[0]**2 + pos[1]**2)\r\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        dirs = (0, 1, 0, -1, 0)\n",
    "        s = {(x, y) for x, y in obstacles}\n",
    "        ans = k = 0\n",
    "        x = y = 0\n",
    "        for c in commands:\n",
    "            if c == -2:\n",
    "                k = (k + 3) % 4\n",
    "            elif c == -1:\n",
    "                k = (k + 1) % 4\n",
    "            else:\n",
    "                for _ in range(c):\n",
    "                    nx, ny = x + dirs[k], y + dirs[k + 1]\n",
    "                    if (nx, ny) in s:\n",
    "                        break\n",
    "                    x, y = nx, ny\n",
    "                    ans = max(ans, x * x + y * y)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        def orientation_change( orient:tuple[int] , command:int) -> tuple[int]:\n",
    "            if command == -2:\n",
    "                return (-orient[1], orient[0])\n",
    "            else:\n",
    "                return (orient[1],-orient[0])\n",
    "        res = 0\n",
    "        prev = (0,0)\n",
    "        obstacles = set( [tuple(i) for i in obstacles] ) #将障碍物存储为元组集合\n",
    "        orient = (0,1)\n",
    "        for i in commands:\n",
    "            if i < 0:\n",
    "                orient = orientation_change( orient, i)\n",
    "            else:\n",
    "                for step in range(1, i + 1 ):\n",
    "                    next_loc = ( prev[0] + orient[0] , prev[1]+orient[1] ) \n",
    "                    if next_loc not in obstacles:\n",
    "                        prev = next_loc\n",
    "                    else:   #遇到障碍则停\n",
    "                        break\n",
    "                res = max(prev[0]*prev[0] + prev[1]*prev[1] , res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "\n",
    "        direction_list = [(1,0), (0,1), (-1,0),(0,-1)]\n",
    "\n",
    "        #集合是哈希表，与字典类似，所以方便查找\n",
    "        obstacles = set([(cur_o[0], cur_o[1]) for cur_o in obstacles])\n",
    "\n",
    "\n",
    "        direction_index = 1\n",
    "        position = [0,0]\n",
    "        max_distance = 0\n",
    "        for cur_command in commands:\n",
    "            if cur_command<0:\n",
    "                direction_index = (direction_index-1)%4 if (cur_command==-1) else (direction_index+1)%4\n",
    "            else:\n",
    "                for i in range(cur_command):\n",
    "                    if (position[0]+direction_list[direction_index][0], position[1]+direction_list[direction_index][1]) in obstacles:\n",
    "                        break\n",
    "                    position = (position[0]+direction_list[direction_index][0], position[1]+direction_list[direction_index][1])\n",
    "                max_distance = max(max_distance, position[0]**2+position[1]**2)\n",
    "        return max_distance\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        #用一个列表记录当前方向信息：共计四个方向可以走\n",
    "        dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]]\n",
    "        px,py,d=0,0,1\n",
    "        mp=set([tuple(i) for i in obstacles])\n",
    "        res=0\n",
    "        for c in commands:\n",
    "            if c<0:\n",
    "                d+=1 if c==-1 else -1\n",
    "                d%=4\n",
    "            else:\n",
    "                for i in range(c):\n",
    "                    if tuple([px + dirs[d][0], py + dirs[d][1]]) in mp:\n",
    "                        break\n",
    "                    px,py=px+dirs[d][0],py+dirs[d][1]\n",
    "                    res=max(res,px*px+py*py)\n",
    "        \n",
    "        \n",
    "        return res\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        dirs = [[-1,0],[0,1],[1,0],[0,-1]]\n",
    "        px ,py ,d = 0,0,1\n",
    "        mp = set([tuple(i) for i in obstacles])\n",
    "        res = 0\n",
    "        for i in commands:\n",
    "            if i<0:\n",
    "                d +=1 if i ==-1 else -1\n",
    "                d %=4\n",
    "            else:\n",
    "                for j in range(i):\n",
    "                    if tuple([px+dirs[d][0],py+dirs[d][1]]) in mp:\n",
    "                        break\n",
    "                    px,py = px+dirs[d][0],py+dirs[d][1]\n",
    "                    res = max(res,px*px+py*py)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        mp = set([tuple(i) for i in obstacles])\n",
    "        res = 0\n",
    "        dire = 0\n",
    "        dx, dy = 0, 0\n",
    "        path = [[0,1], [1,0], [0,-1],[-1,0]]\n",
    "        flag = 0\n",
    "        for c in commands:\n",
    "            if c < 0:\n",
    "                if c == -1:\n",
    "                    flag += 1\n",
    "                else:\n",
    "                    flag -= 1\n",
    "                flag = flag % 4\n",
    "            else:\n",
    "                for _ in range(c):\n",
    "                    if tuple([dx+path[flag][0], dy+path[flag][1]]) in mp:\n",
    "                        break\n",
    "                    dx = dx+path[flag][0]\n",
    "                    dy = dy+path[flag][1]\n",
    "                    res = max(res, dx**2+dy**2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        direction = ((0, 1), (1, 0), (0, -1), (-1, 0))\n",
    "        d = 0\n",
    "        cur = (0 , 0)\n",
    "        obs = set([tuple(i) for i in obstacles])\n",
    "        ans = 0\n",
    "\n",
    "        for cmd in commands:\n",
    "            if cmd == -1:\n",
    "                d = (d + 1) % 4\n",
    "            elif cmd == -2:\n",
    "                d = (d - 1) % 4\n",
    "            else:\n",
    "                dx, dy = direction[d]\n",
    "                x, y = cur\n",
    "                while cmd > 0:\n",
    "                    if (x + dx, y + dy) in obs:\n",
    "                        break\n",
    "                    x, y = x + dx, y + dy\n",
    "                    cmd -= 1\n",
    "                cur = (x, y)\n",
    "                ans = max(ans, x * x + y * y)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "                dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]]\n",
    "                px, py, d = 0, 0, 1\n",
    "                mp = set([tuple(i) for i in obstacles])\n",
    "                res = 0\n",
    "                for c in commands:\n",
    "                    if c < 0:\n",
    "                        d += 1 if c == -1 else -1\n",
    "                        d %= 4\n",
    "                    else:\n",
    "                        for i in range(c):\n",
    "                            if tuple([px + dirs[d][0], py + dirs[d][1]]) in mp:\n",
    "                                break\n",
    "                            px, py = px + dirs[d][0], py + dirs[d][1]\n",
    "                            res = max(res, px * px + py * py)\n",
    "                return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def GetFxPos(self, pos, fx):\n",
    "        pos1 = []\n",
    "        if fx == 1:\n",
    "            pos1 = [pos[0] , pos[1]+1]\n",
    "        elif fx == 2:\n",
    "            pos1 = [pos[0]+1, pos[1] ]\n",
    "        elif fx == 3:\n",
    "            pos1 = [pos[0] , pos[1]-1]\n",
    "        elif fx == 4:\n",
    "            pos1 = [pos[0]-1, pos[1] ]\n",
    "        return pos1\n",
    "        \n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        dict={}\n",
    "        for item in obstacles:\n",
    "            dict[str(item[0])+','+str(item[1])]=1\n",
    "        path=[]\n",
    "        mx=0\n",
    "        pos=[0,0]\n",
    "        fx=1\n",
    "        for i in range(len(commands)):\n",
    "            cmd=commands[i]\n",
    "            if cmd==-1:\n",
    "                fx+=1\n",
    "                if fx==5:fx=1\n",
    "            elif cmd==-2:\n",
    "                fx-=1\n",
    "                if fx==0:fx=4\n",
    "            else:\n",
    "                for j in range(cmd):\n",
    "                    tpos=self.GetFxPos(pos,fx)\n",
    "                    if str(tpos[0]) +','+ str(tpos[1]) not in dict.keys():\n",
    "                        pos=tpos\n",
    "                        path.append(pos[0]**2+pos[1]**2)\n",
    "                        mx=max(mx,pos[0]**2+pos[1]**2)\n",
    "                    else:\n",
    "                        break\n",
    "        return mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        DIRECTIONS = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n",
    "        look_up = set([tuple(i) for i in obstacles])\n",
    "        px, py, d = 0, 0, 0\n",
    "\n",
    "        res = 0\n",
    "        for command in commands:\n",
    "            if command < 0:\n",
    "                d += 1 if command == -1 else -1\n",
    "                d %= 4\n",
    "            else:\n",
    "                for _ in range(command):\n",
    "                    if (px + DIRECTIONS[d][0], py + DIRECTIONS[d][1]) in look_up:\n",
    "                        break\n",
    "                    px += DIRECTIONS[d][0]\n",
    "                    py += DIRECTIONS[d][1]\n",
    "        \n",
    "                    res = max(res, px ** 2 + py ** 2)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]]\n",
    "        px, py, d = 0, 0, 1\n",
    "        mp = set([tuple(i) for i in obstacles])\n",
    "        res = 0\n",
    "        for c in commands:\n",
    "            if c < 0:\n",
    "                d += 1 if c == -1 else -1\n",
    "                d %= 4\n",
    "            else:\n",
    "                for i in range(c):\n",
    "                    if tuple([px + dirs[d][0], py + dirs[d][1]]) in mp:\n",
    "                        break\n",
    "                    px, py = px + dirs[d][0], py + dirs[d][1]\n",
    "                    res = max(res, px * px + py * py)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def GetFxPos(self, pos, fx):\n",
    "        pos1 = []\n",
    "        if fx == 1:\n",
    "            pos1 = [pos[0] , pos[1]+1]\n",
    "        elif fx == 2:\n",
    "            pos1 = [pos[0]+1, pos[1] ]\n",
    "        elif fx == 3:\n",
    "            pos1 = [pos[0] , pos[1]-1]\n",
    "        elif fx == 4:\n",
    "            pos1 = [pos[0]-1, pos[1] ]\n",
    "        return pos1\n",
    "        \n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        dict={}\n",
    "        for item in obstacles:\n",
    "            dict[str(item[0])+','+str(item[1])]=1\n",
    "        path=[]\n",
    "        mx=0\n",
    "        pos=[0,0]\n",
    "        fx=1\n",
    "        for i in range(len(commands)):\n",
    "            cmd=commands[i]\n",
    "            if cmd==-1:\n",
    "                fx+=1\n",
    "                if fx==5:fx=1\n",
    "            elif cmd==-2:\n",
    "                fx-=1\n",
    "                if fx==0:fx=4\n",
    "            else:\n",
    "                for j in range(cmd):\n",
    "                    tpos=self.GetFxPos(pos,fx)\n",
    "                    if str(tpos[0]) +','+ str(tpos[1]) not in dict.keys():\n",
    "                        pos=tpos\n",
    "                        path.append(pos[0]**2+pos[1]**2)\n",
    "                        mx=max(mx,pos[0]**2+pos[1]**2)\n",
    "        return mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        direction = 0\n",
    "        x = 0\n",
    "        y = 0\n",
    "        res = 0\n",
    "        obstacles_x = {}\n",
    "        obstacles_y = {}\n",
    "        for ob in obstacles:\n",
    "            if ob[0] not in obstacles_x:\n",
    "                obstacles_x[ob[0]] = [ob]\n",
    "            else:\n",
    "                obstacles_x[ob[0]].append(ob)\n",
    "            if ob[1] not in obstacles_y:\n",
    "                obstacles_y[ob[1]] = [ob]\n",
    "            else:\n",
    "                obstacles_y[ob[1]].append(ob)\n",
    "\n",
    "        for command in commands:\n",
    "            if command == -1:\n",
    "                direction = {0: 1, 1: 2, 2: 3, 3: 0}[direction]\n",
    "            elif command == -2:\n",
    "                direction = {0: 3, 1: 0, 2: 1, 3: 2}[direction]\n",
    "            else:\n",
    "                if direction in [0, 2]:\n",
    "                    start = y + (1-direction)\n",
    "                    end = y + (1-direction) * command\n",
    "                    mindistance = 10000000\n",
    "                    if x in obstacles_x:\n",
    "                        for obstacle in obstacles_x[x]:\n",
    "                            if obstacle[0] == x and obstacle[1] <= (max(start, end)) and obstacle[1] >= (min(start, end))  and abs(obstacle[1] - start) < mindistance:\n",
    "                                mindistance = abs(obstacle[1] - start)\n",
    "\n",
    "                    if mindistance == 10000000:\n",
    "                        y = end\n",
    "                    else:\n",
    "                        y = y + (1-direction) * mindistance\n",
    "                elif direction in [1, 3]:\n",
    "                    start = x + (2-direction)\n",
    "                    end = x + (2-direction) * command\n",
    "                    mindistance = 10000000\n",
    "\n",
    "                    if y in obstacles_y:\n",
    "                        for obstacle in obstacles_y[y]:\n",
    "                            if obstacle[1] == y and obstacle[0] <= (max(start, end)) and obstacle[0] >= (min(start, end))  and abs(obstacle[0] - start) < mindistance:\n",
    "                                mindistance = abs(obstacle[0] - start)\n",
    "\n",
    "                    if mindistance == 10000000:\n",
    "                        x = end\n",
    "                    else:\n",
    "                        x = x + (2-direction) * mindistance\n",
    "            res = max(res, (x**2+y**2))\n",
    "            # print(x, y)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands, obstacles):\n",
    "        directions = ((0, 1), (1, 0), (0, -1), (-1, 0)) # -1=right which is +1 in directions, -2=left which is -1 in directions\n",
    "        currentdir = 0\n",
    "        dic = {}\n",
    "        for ob in obstacles:\n",
    "            if ob[0] not in dic:\n",
    "                dic[ob[0]] = {ob[1]: 0}\n",
    "            else:\n",
    "                dic[ob[0]][ob[1]] = 0\n",
    "        currentPlace = (0, 0)\n",
    "        result = 0\n",
    "        for i in range(len(commands)):\n",
    "            if commands[i] == -1:\n",
    "                currentdir = (currentdir + 1) % 4\n",
    "            elif commands[i] == -2:\n",
    "                currentdir = (currentdir + 4 - 1) % 4\n",
    "            else:\n",
    "                for j in range(commands[i]):\n",
    "                    target = (currentPlace[0] + directions[currentdir][0], currentPlace[1] + directions[currentdir][1])\n",
    "                    if target[0] in dic and target[1] in dic[target[0]]:\n",
    "                        break\n",
    "                    else:\n",
    "                        currentPlace = target\n",
    "                        result = max(result, target[0]**2+target[1]**2)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        # s = set(obstacles)\n",
    "        # horital = defaultdict(SortedList)\n",
    "        # vertical = defaultdict(SortedList)\n",
    "        # for x, y in obstacles:\n",
    "        #     horital[x].add(y)\n",
    "        #     vertical[y].add(x)\n",
    "        s = set([(o[0], o[1]) for o in obstacles])\n",
    "        # print(\"s = \", s)\n",
    "        dir = [(0, 1), (-1, 0), (0, -1), (1, 0)]\n",
    "        num = 0\n",
    "        n = len(commands)\n",
    "        ori = [0, 0]\n",
    "        res = 0\n",
    "        \n",
    "        for i in commands:\n",
    "            if i == -2:\n",
    "                num = (num + 1) % 4\n",
    "            elif i == -1:\n",
    "                num = (num - 1 + 4) % 4\n",
    "            else:\n",
    "                for _ in range(i):\n",
    "                    tmp = (ori[0] + dir[num][0], ori[1] + dir[num][1])\n",
    "                    if tmp in s:\n",
    "                        break\n",
    "                    ori = tmp\n",
    "                # print(\"i = \", i)\n",
    "                # print(\"ori = \", ori)\n",
    "                res = max(res, ori[0] * ori[0] + ori[1] * ori[1])\n",
    "                # print(\"res = \", res)\n",
    "        return res\n",
    "                \n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from dataclasses import dataclass\n",
    "from enum import Enum, unique\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "\n",
    "        @dataclass(eq=True, frozen=True)\n",
    "        class Point:\n",
    "            fields = ('x', 'y')\n",
    "            x: int\n",
    "            y: int\n",
    "\n",
    "            def distance(self) -> int:\n",
    "                return self.x ** 2 + self.y ** 2\n",
    "        \n",
    "            def __iter__(self):\n",
    "                yield self.x\n",
    "                yield self.y\n",
    "\n",
    "        @unique\n",
    "        class Direction(Enum):\n",
    "            Up = 0\n",
    "            Bottom = 1\n",
    "            Left = 2\n",
    "            Right = 3\n",
    "\n",
    "            def turn_left(self) -> 'Direction':\n",
    "                match self:\n",
    "                    case Direction.Up:\n",
    "                        return Direction.Left\n",
    "                    case Direction.Bottom:\n",
    "                        return Direction.Right\n",
    "                    case Direction.Left:\n",
    "                        return Direction.Bottom\n",
    "                    case Direction.Right:\n",
    "                        return Direction.Up\n",
    "\n",
    "            def turn_right(self) -> 'Direction':\n",
    "                match self:\n",
    "                    case Direction.Up:\n",
    "                        return Direction.Right\n",
    "                    case Direction.Right:\n",
    "                        return Direction.Bottom\n",
    "                    case Direction.Bottom:\n",
    "                        return Direction.Left\n",
    "                    case Direction.Left:\n",
    "                        return Direction.Up\n",
    "            \n",
    "            def next(self, p: Point) -> Point:\n",
    "                x, y = p\n",
    "                match self:\n",
    "                    case Direction.Up:\n",
    "                        return Point(x, y + 1)\n",
    "                    case Direction.Right:\n",
    "                        return Point(x + 1, y)\n",
    "                    case Direction.Left:\n",
    "                        return Point(x - 1, y)\n",
    "                    case Direction.Bottom:\n",
    "                        return Point(x, y - 1)\n",
    "            \n",
    "        h = set(map(lambda v: Point(v[0], v[1]), obstacles))\n",
    "        ans = 0\n",
    "        current = Point(0, 0)\n",
    "        direction = Direction.Up\n",
    "\n",
    "        for command in commands:\n",
    "            match command:\n",
    "                case -2:\n",
    "                    direction = direction.turn_left()\n",
    "                case -1:\n",
    "                    direction = direction.turn_right()\n",
    "                case d:\n",
    "                    for _ in range(d):\n",
    "                        nxt = direction.next(current)\n",
    "                        if nxt in h:\n",
    "                            break\n",
    "                        current = nxt\n",
    "                    \n",
    "                    ans = max(ans, current.distance())\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        dirs = [[-1, 0], [0, 1], [1, 0], [0, -1]]\n",
    "        px, py, d = 0, 0, 1\n",
    "        mp = set([tuple(i) for i in obstacles])\n",
    "        print(mp)\n",
    "        res = 0\n",
    "        for c in commands:\n",
    "            if c < 0:\n",
    "                d += 1 if c == -1 else -1\n",
    "                d %= 4\n",
    "            else:\n",
    "                for i in range(c):\n",
    "                    if tuple([px + dirs[d][0], py + dirs[d][1]]) in mp:\n",
    "                        break\n",
    "                    px, py = px + dirs[d][0], py + dirs[d][1]\n",
    "                    res = max(res, px * px + py * py)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def robotSim(self, commands: list[int], obstacles: list[list[int]]) -> int:\n",
    "        mapX={}\n",
    "        mapY={}\n",
    "        ans=0\n",
    "        nowPos=[0,0]\n",
    "        nowDir=0\n",
    "\n",
    "        for obstacle in obstacles:\n",
    "\n",
    "\n",
    "            if obstacle[0] in mapX:\n",
    "                mapX[obstacle[0]].append(obstacle[1])\n",
    "            else:\n",
    "                mapX[obstacle[0]]=[obstacle[1]]\n",
    "            if obstacle[1] in mapY:\n",
    "                mapY[obstacle[1]].append(obstacle[0])\n",
    "            else:\n",
    "                mapY[obstacle[1]]=[obstacle[0]]\n",
    "\n",
    "        for k in mapX:\n",
    "            mapX[k].sort()\n",
    "        for k in mapY:\n",
    "            mapY[k].sort()\n",
    "        for command in commands:\n",
    "            if command==-2:\n",
    "                nowDir=(nowDir-1)%4\n",
    "            elif command==-1:\n",
    "                nowDir=(nowDir+1)%4\n",
    "            else:\n",
    "                if nowDir==0:\n",
    "                    finalY=nowPos[1]+command\n",
    "                    if nowPos[0] in mapX:\n",
    "                        findIndex=bisect.bisect_right(mapX[nowPos[0]],nowPos[1])\n",
    "\n",
    "\n",
    "                        if findIndex<len(mapX[nowPos[0]]) and mapX[nowPos[0]][findIndex]<=finalY:\n",
    "                                finalY=mapX[nowPos[0]][findIndex]-1\n",
    "\n",
    "                    nowPos=[nowPos[0],finalY]\n",
    "                elif nowDir==2:\n",
    "                    finalY=nowPos[1]-command\n",
    "                    if nowPos[0] in mapX:\n",
    "                        findIndex=bisect.bisect_left(mapX[nowPos[0]],nowPos[1])\n",
    "                        if findIndex>0 and mapX[nowPos[0]][findIndex-1]>=finalY:\n",
    "                            finalY=mapX[nowPos[0]][findIndex-1]+1\n",
    "\n",
    "                    nowPos=[nowPos[0],finalY]\n",
    "                elif nowDir==1:\n",
    "\n",
    "                    finalX=nowPos[0]+command\n",
    "                    if nowPos[1] in mapY:\n",
    "                        findIndex=bisect.bisect_right(mapY[nowPos[1]],nowPos[0])\n",
    "                        if findIndex<len(mapY[nowPos[1]]) and mapY[nowPos[1]][findIndex]<=finalX:\n",
    "                            finalX=mapY[nowPos[1]][findIndex]-1\n",
    "\n",
    "                    nowPos=[finalX,nowPos[1]]\n",
    "                else:\n",
    "\n",
    "                    finalX=nowPos[0]-command\n",
    "                    if nowPos[1] in mapY:\n",
    "                        findIndex=bisect.bisect_left(mapY[nowPos[1]],nowPos[0])\n",
    "                        if findIndex>0 and mapY[nowPos[1]][findIndex-1]>=finalX:\n",
    "                            finalX=mapY[nowPos[1]][findIndex-1]+1\n",
    "\n",
    "                    nowPos=[finalX,nowPos[1]]\n",
    "\n",
    "\n",
    "                ans=max(ans,nowPos[0]**2+nowPos[1]**2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def robotSim(self, commands: list[int], obstacles: list[list[int]]) -> int:\n",
    "        mapX={}\n",
    "        mapY={}\n",
    "        ans=0\n",
    "        nowPos=[0,0]\n",
    "        nowDir=0\n",
    "\n",
    "        for obstacle in obstacles:\n",
    "\n",
    "\n",
    "            if obstacle[0] in mapX:\n",
    "                mapX[obstacle[0]].append(obstacle[1])\n",
    "            else:\n",
    "                mapX[obstacle[0]]=[obstacle[1]]\n",
    "            if obstacle[1] in mapY:\n",
    "                mapY[obstacle[1]].append(obstacle[0])\n",
    "            else:\n",
    "                mapY[obstacle[1]]=[obstacle[0]]\n",
    "\n",
    "        for k in mapX:\n",
    "            mapX[k].sort()\n",
    "        for k in mapY:\n",
    "            mapY[k].sort()\n",
    "        for command in commands:\n",
    "            if command==-2:\n",
    "                nowDir=(nowDir-1)%4\n",
    "            elif command==-1:\n",
    "                nowDir=(nowDir+1)%4\n",
    "            else:\n",
    "                if nowDir==0:\n",
    "                    finalY=nowPos[1]+command\n",
    "                    if nowPos[0] in mapX:\n",
    "                        findIndex=bisect.bisect_right(mapX[nowPos[0]],nowPos[1])\n",
    "\n",
    "\n",
    "                        if findIndex<len(mapX[nowPos[0]]) and mapX[nowPos[0]][findIndex]<=finalY:\n",
    "                                finalY=mapX[nowPos[0]][findIndex]-1\n",
    "\n",
    "                    nowPos=[nowPos[0],finalY]\n",
    "                elif nowDir==2:\n",
    "                    finalY=nowPos[1]-command\n",
    "                    if nowPos[0] in mapX:\n",
    "                        findIndex=bisect.bisect_left(mapX[nowPos[0]],nowPos[1])\n",
    "                        if findIndex>0 and mapX[nowPos[0]][findIndex-1]>=finalY:\n",
    "                            finalY=mapX[nowPos[0]][findIndex-1]+1\n",
    "\n",
    "                    nowPos=[nowPos[0],finalY]\n",
    "                elif nowDir==1:\n",
    "\n",
    "                    finalX=nowPos[0]+command\n",
    "                    if nowPos[1] in mapY:\n",
    "                        findIndex=bisect.bisect_right(mapY[nowPos[1]],nowPos[0])\n",
    "                        if findIndex<len(mapY[nowPos[1]]) and mapY[nowPos[1]][findIndex]<=finalX:\n",
    "                            finalX=mapY[nowPos[1]][findIndex]-1\n",
    "\n",
    "                    nowPos=[finalX,nowPos[1]]\n",
    "                else:\n",
    "\n",
    "                    finalX=nowPos[0]-command\n",
    "                    if nowPos[1] in mapY:\n",
    "                        findIndex=bisect.bisect_left(mapY[nowPos[1]],nowPos[0])\n",
    "                        if findIndex>0 and mapY[nowPos[1]][findIndex-1]>=finalX:\n",
    "                            finalX=mapY[nowPos[1]][findIndex-1]+1\n",
    "\n",
    "                    nowPos=[finalX,nowPos[1]]\n",
    "\n",
    "\n",
    "                ans=max(ans,nowPos[0]**2+nowPos[1]**2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        from collections import defaultdict\n",
    "        obs = defaultdict(set)\n",
    "        for x, y in obstacles:\n",
    "            obs[x].add(y)\n",
    "        dir = [[0,1], [1,0], [0,-1], [-1, 0]]\n",
    "        pd = 0\n",
    "        cx, cy = 0, 0\n",
    "        res = 0\n",
    "        for p in commands:\n",
    "            if p == -2:\n",
    "                pd = (pd+3)%4\n",
    "            elif p == -1:\n",
    "                pd = (pd+1)%4\n",
    "            else:\n",
    "                for k in range(p):\n",
    "                    nx, ny = cx+dir[pd][0], cy+dir[pd][1]\n",
    "                    if nx in obs and ny in obs[nx]:\n",
    "                        break\n",
    "                    cx, cy = nx, ny\n",
    "                res = max(res, cx*cx+cy*cy)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        max_len = 0\n",
    "        loc = [0,0]\n",
    "        dict_row = {}\n",
    "        dict_col = {}\n",
    "        for k in obstacles:\n",
    "            if k[1] not in dict_row:\n",
    "                dict_row[k[1]] = [k[0]]\n",
    "            else:\n",
    "                dict_row[k[1]].append(k[0])\n",
    "\n",
    "            if k[0] not in dict_col:\n",
    "                dict_col[k[0]] = [k[1]]\n",
    "            else:\n",
    "                #print(k)\n",
    "                dict_col[k[0]].append(k[1])\n",
    "        #print(dict_col)\n",
    "        #print(dict_row)\n",
    "\n",
    "        direct = 0 #0 n 1 w 2 s 3 e\n",
    "        for i in commands:\n",
    "            if i == -1:\n",
    "                if direct == 0:\n",
    "                    direct = 3\n",
    "                else:\n",
    "                    direct = direct - 1\n",
    "            elif i == -2:\n",
    "                if direct == 3:\n",
    "                    direct = 0\n",
    "                else:\n",
    "                    direct = direct + 1\n",
    "            else:\n",
    "                if direct == 0:\n",
    "                    a = loc[1]+i\n",
    "                    if loc[0] in dict_col:\n",
    "                        print(dict_col[loc[0]])\n",
    "                        for j in range(1,i+1):\n",
    "                            if loc[1]+j in dict_col[loc[0]]:\n",
    "                                a = loc[1] + j - 1\n",
    "                                break\n",
    "                    loc[1] = a\n",
    "\n",
    "                if direct == 1:\n",
    "                    a = loc[0]-i\n",
    "                    if loc[1] in dict_row:\n",
    "                        #print(loc[1],i,dict_row[loc[1]])\n",
    "                        for j in range(1,i+1):\n",
    "                            if loc[0]-j in dict_row[loc[1]]:\n",
    "                                a = loc[0] - j +1\n",
    "                                break\n",
    "                    loc[0] = a\n",
    "\n",
    "                if direct == 2:\n",
    "                    a = loc[1]-i\n",
    "                    if loc[0] in dict_col:\n",
    "                        for j in range(1,i+1):\n",
    "                            if loc[1]-j in dict_col[loc[0]]:\n",
    "                                a = loc[1] - j + 1\n",
    "                                break\n",
    "                    loc[1] = a\n",
    "\n",
    "                if direct == 3:\n",
    "                    a = loc[0]+i\n",
    "                    if loc[1] in dict_row:\n",
    "                        #print(\"aa\",dict_row,loc[0])\n",
    "                        for j in range(1,i+1):\n",
    "                            if loc[0]+j in dict_row[loc[1]]:\n",
    "                                a = loc[0] + j -1\n",
    "                                break\n",
    "                    loc[0] = a\n",
    "            print(i,loc,direct)\n",
    "            print(max_len)\n",
    "            if loc[0]*loc[0]+loc[1]*loc[1] > max_len:\n",
    "                max_len = loc[0]*loc[0]+loc[1]*loc[1]\n",
    "\n",
    "        return max_len"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands, obstacles):\n",
    "        locations = [0, 0]\n",
    "        direction = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        idx_direct = 0\n",
    "        obs_dict_x = {}\n",
    "        obs_dict_y = {}\n",
    "        max_distance = 0\n",
    "        for x, y in obstacles:\n",
    "            if x in obs_dict_x:\n",
    "                obs_dict_x[x].append(y)\n",
    "            else:\n",
    "                obs_dict_x[x] = [y]\n",
    "            if y in obs_dict_y:\n",
    "                obs_dict_y[y].append(x)\n",
    "            else:\n",
    "                obs_dict_y[y] = [x]\n",
    "        for item in commands:\n",
    "            if item == -1:\n",
    "                idx_direct = (idx_direct + 1) % 4\n",
    "            elif item == -2:\n",
    "                idx_direct = (idx_direct - 1) % 4\n",
    "            else:\n",
    "                new_location = [None, None]\n",
    "                new_location[0] = locations[0] + item * direction[idx_direct][0]\n",
    "                new_location[1] = locations[1] + item * direction[idx_direct][1]\n",
    "                if idx_direct == 0 or idx_direct == 2:\n",
    "                    if new_location[0] in obs_dict_x:\n",
    "                        temp_obs = obs_dict_x[new_location[0]]\n",
    "                        for i in range(locations[1] + direction[idx_direct][1], new_location[1] + direction[idx_direct][1], direction[idx_direct][1]):\n",
    "                            if i in temp_obs:\n",
    "                                new_location[1] = i - direction[idx_direct][1]\n",
    "                                break\n",
    "                else:\n",
    "                    if new_location[1] in obs_dict_y:\n",
    "                        temp_obs = obs_dict_y[new_location[1]]\n",
    "                        for i in range(locations[0] + direction[idx_direct][0], new_location[0] + direction[idx_direct][0], direction[idx_direct][0]):\n",
    "                            if i in temp_obs:\n",
    "                                new_location[0] = i - direction[idx_direct][0]\n",
    "                                break\n",
    "                locations[0], locations[1] = new_location[0], new_location[1]\n",
    "                max_distance = max(max_distance, locations[0] ** 2 + locations[1] ** 2)\n",
    "        return max_distance\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
